Algorithm Solution4 [KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회) 이 풀이는 homebody님의 풀이를 보고 이해하며 작성한 것입니다. 처음에는 줄세우기 문제와 비슷하다고 생각했는데, 누가 더 잘 하고, 못하고에 맞춰서 정렬하는 건 쉽지만 그 범위를 알아내는 건 어려웠다. 그래서 반대로 root 노드로부터 떨어진 거리를 각각 기록하고, 각 정점의 자식 수를 기록해서 같은 거리에 있는 그래프들의 순위 변화에 따라서 어떻게 등수가 바뀌는지 계산하려고 했지만 구현이 까다로울 뿐더러 연결 그래프가 2개 이상인 경우에는 답도 구할 수 없어서 결국 풀이를 봤다. 아이디어는 간단한데, 그래프를 두 개로 분리해서 "나보다 등수가 높은 그래프"와 "나보다 등수가 낮은 그래프"로 관리하는 것이다. (이걸 어떻게 생각했을까...) 예를 들어서 경민이가 형곤이보다 등수가 높다고 해보자. 그.. 2019. 12. 28. [KOI 초등부] BOJ 17614 369 (2019 2차 대회) 17614번: 369 민수는 같은 반 친구들과 369게임을 하고 있다. 369게임은 여러 명이 원형으로 둘러 앉아 시작 위치의 사람이 1을 외치며 시작된다. 이후 시계방향으로 돌아가며 2, 3, 4와 같이 1씩 증가된 수가 자기 수가 된다. 순서대로 돌아오는 자기 수에 3, 6, 혹은 9가 포함되어 있지 않다면 그 수를 말해야 하며, 3, 6, 혹은 9가 포함되어 있으면 그 개수만큼 박수를 쳐야 한다. 이 규칙을 지키지 못하면 게임이 종료된다. 민수는 369게임이 N까지 규칙 www.acmicpc.net 문제 유형 : ad-hoc or 간단한 DP 369 게임에서 N번째 숫자를 부르기 까지 박수를 몇 번 쳐야하는지 구하는 문제로, 다음과 같이 풀었다. 1. 임의의 숫자 K에 대해서 박수를 치는 횟수를 구.. 2019. 12. 28. [KOI 초등부 / 메모리초과] BOJ 17609 회문 (2019 1차 대회) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 유형 : DP라고 생각했는데 좀 더 생각해봐야겠다. DP로 풀려니까 N = 100,000인데다가 O(N^2)이라 안풀린다. 흠. 2019. 12. 25. [KOI 초등부] BOJ 17608 막대기 (2019 1차 대회) 불러오는 중입니다... 문제 유형 : 개인적으론 ad-hoc인듯 해설 : 먼저 막대기의 길이를 배열에 저장, 막대기의 개수가 N이라고 했을때 오른쪽에서 바라보므로 N-1, N-2, ... , 0 이렇게 마지막 원소부터 차례대로 순회를 하는데, "지금까지 순회한 막대기 중 가장 긴 것"보다 길이가 긴 경우에만 개수를 더해주면 된다. 지금까지 순회한 막대기 중 가장 큰 것 보다 작거나 같은 경우는 눈에 보이지 않기 때문 문제의 테스트 케이스를 직접 그려보면 이해가 잘 된다. 구현 : 2019. 12. 25. 이전 1 다음
