[백준 03996] 위대한 사기꾼 [Python]

문제

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

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

음의 진법은 사람들이 이해하기는 어렵다. 따라서, 상근이는 달을 여행하는 동안 0과 𝑛을 포함하는 사이의 수 중에서 𝑘진법과 −𝑘진법에서 표현이 같은 수를 모두 외웠다. 상근이가 외운 숫자의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 𝑛과 𝑘가 주어진다. (1 ≤ 𝑛 ≤ 10^15, 2 ≤ 𝑘 ≤ 1,000)

출력

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

---

풀이

K진법과 -K진법으로 표현한 수가 표현이 동일한 경우를 세는 문제다.

-K진법에 대해 K^(odd) 자릿수가 0인 경우 K진법과 동일하다는 특징이 있다.

K진수로 변화한 N에 대해 조건에 부합한 수를 찾고자 한다.

만약 변화한 N이 1011101인 경우 K^3자릿수에 1이 있으므로 0000000 ~ 1010000 수들에 대해서 찾으면 된다.

조건에 부합하는 수를 세기 위해 K^(0 or even) 자릿수를 활용하면 되지만 K진수에 대한 계산으로는 식이 복잡해진다.

때문에 K^2진수에 대한 풀이 방법을 선택했다.

우선 주어진 수를 K^2진수로 변환해주자.

역순으로 탐색하며 자릿수의 수가 K보다 작은 경우에만 자릿수의 수를 활용해 K^(odd)가 0인 경우를 제외한 나머지를 세어주자.

만약 자릿수의 수가 K이상이라면, 1011101의 예시처럼 뒤에 오는 자릿수의 수를 전부 무시하고, 앞의 수 까지만 세어주어야 한다. 자릿수의 수를 전부 무시하니, K^(남은 자릿수 - 1)을 곱해주고 break를 걸어 비정상종료를 해주자. 

만약 비정상 종료가 되지않고 반복문이 끝까지 돌았다면 주어진 N의 K, -K진수 형태가 동일하다는 의미이다.

마지막에 곱한 K는 불필요하니 다시 나누고 1을 더해주자.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/3996