위대한 사기꾼 - 3996

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	322	81	67	32.367%

문제

믿기 힘들겠지만 상근이는 이번 겨울 방학에 달에 갔다 왔다. 방학이 끝나고 다시 학교로 돌아온 상근이는 친구들에게 달나라 사람(Selenites)을 만났던 이야기를 해주었다.

상근이는 달에서 사용하는 수 체계를 주로 설명해주었다. 달에서는 음의 진법을 사용한다.

입력

출력

첫째 줄에 상근이가 달에서 생활하면서 외운 숫자의 개수를 출력한다.

예제 입력 1

21 3

예제 출력 1

9

예제 입력 2

21 2

예제 출력 2

8

힌트

첫 번째 예제에서 상근이는 0, 1, 2, 9, 10, 11, 18, 19, 20을 외웠다.

19는 3진법과 -3진법에서 19 = 2013 = 201-3으로 표현이 같다. 하지만, 7은 7 = 213 = 111-3으로 같지 않다.

두 번째 예제의 경우에는 0, 1, 4, 5, 16, 17, 20, 21을 외우면 된다.

 

Solution

https://github.com/anothel/BOJ/blob/main/python/3966_ExcellentTrickster.py

GitHub - anothel/BOJ

 

후기

나누기를 하고 나서 몫을 내리는 새로운 연산자(//=)를 알게 됐다. 반드시 필요한 연산자로써 math를 import 해서도 사용할 수도 있다. 연산자는 둘째 치고, 이 문제는 동적 계획법을 사용한 알고리즘 문제였는데, 상당히 어려웠다. K, -K진법을 구하는 방법을 알아야 하며, 음수 진법을 깨달은 후 각각 구해서 비교를 해봤다. 결과는 시간 초과.

 

n의 범위가 1부터 1000000000000000까지였기 때문에 직접 구한 후 서로 비교하는 것은 제한 시간 내에 불가능했다(다음부터는 최대 범위부터 넣어서 테스트를 해봐야겠다.). 직접 비교가 아니라면 문제에서 원하는 답을 찾기 위한 규칙을 찾아야 하는데(이게 동적 계획법, Dynamic Programming), 못 찾겠다.

 

답을 못 찾아서 답을 구하는 방법을 찾아보다가 결국, 딱 한 개의 해설을 찾았다. 이 사람은 어떻게 풀었는지, 이 사람을 따라갈 수가 없었다(아직 나는 한참 멀었다.). 그냥 끝내도 되긴 하지만, 대체 이 사람은 어떻게 답을 찾아갔는지 너무 궁금했기에, 그 궁금증은 해결하기 위해서 댓글을 달았다. 부끄럽지만, 모르는 채로 두는 게 훨씬 부끄럽다고 생각한다.

 

(url: https://www.acmicpc.net/problem/3996, https://b0neh3ad.github.io/boj/boj-3996/, https://m.blog.naver.com/dylan0301/221785998279)