본문 바로가기

KOI초등부

[KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회) 이 풀이는 homebody님의 풀이를 보고 이해하며 작성한 것입니다. 처음에는 줄세우기 문제와 비슷하다고 생각했는데, 누가 더 잘 하고, 못하고에 맞춰서 정렬하는 건 쉽지만 그 범위를 알아내는 건 어려웠다. 그래서 반대로 root 노드로부터 떨어진 거리를 각각 기록하고, 각 정점의 자식 수를 기록해서 같은 거리에 있는 그래프들의 순위 변화에 따라서 어떻게 등수가 바뀌는지 계산하려고 했지만 구현이 까다로울 뿐더러 연결 그래프가 2개 이상인 경우에는 답도 구할 수 없어서 결국 풀이를 봤다. 아이디어는 간단한데, 그래프를 두 개로 분리해서 "나보다 등수가 높은 그래프"와 "나보다 등수가 낮은 그래프"로 관리하는 것이다. (이걸 어떻게 생각했을까...) 예를 들어서 경민이가 형곤이보다 등수가 높다고 해보자. 그.. 더보기
[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에 대해서 박수를 치는 횟수를 구.. 더보기