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에 대해서 박수를 치는 횟수를 구하는 함수를 만든다.
2. 1~N까지 1에서 만든 함수를 돌려서 더한다.
DP로 더 빠르게 풀 수 있을 것 같긴 한데, 1번에서 만든 함수는 숫자의 자릿수 만큼 연산하므로 O(7) = O(1)로 해석할 수 있다. 그럼 O(1) * O(N)이므로 O(N)안에 풀려서 그냥 풀었다.
구현
'Algorithm Solution > KOI Elementary School' 카테고리의 다른 글
| [KOI 초등부] BOJ 17616 등수 찾기 (2019 2차 대회) (3) | 2019.12.28 |
|---|---|
| [KOI 초등부 / 메모리초과] BOJ 17609 회문 (2019 1차 대회) (0) | 2019.12.25 |
| [KOI 초등부] BOJ 17608 막대기 (2019 1차 대회) (0) | 2019.12.25 |
댓글