[BOJ](Python) 1975번 : Number Game

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

1975번: Number Game

12를 예를 들어보자.

12를 2진수로 변환하면,

12를 2진법으로 변환했을 때

우선 6을 2진수로 변환하면,

6을 2진법으로 변환하였을 때

마지막으로 3을 2진수로 변환하면,

3을 2진법으로 변환하였을 때

이 된다. 식을 잘 보면 12를 2로 나눴을때 나머지가 0이고, 6을 2로 나눴을 때 나머지가 0, 하지만 3을 2로 나눴을 때 나머지가 0이 된다. 이러한 규칙을 보았을 때, n을 k(진법)으로 나눴을 때 나머지가 0이라면 맨 뒤가 0고, 그렇지 않다면 0이 아닌 다른 수가 오는 것을 알 수 있다.

 

코드를 보면 다음과 같다.

import sys
input = sys.stdin.readline

def func(x, b):
    if x !=0 and x % b == 0: return 1+func(x//b,b)
    else: return 0

c = [0] * 1001
for x in range(2, 1001):
    c[x] = sum(func(x, b) for b in range(2, x+1))

for _ in range(int(input())):
    x = int(input())
    print(c[x])

먼저,

for x in range(2, 1001):
    c[x] = sum(func(x, b) for b in range(2, x+1))

x을 x진법으로 변환하면 10(x진법)이 된다. 그리고 x+1 진법으로 변환하게 되면 n(x+1진법)이 되므로 맨 뒤에 0이 존재할 수 없다. 따라서 x를 b진법으로 변환하는 과정에서 b의 최댓값을 x로 한정한다. 그렇게 각 진법에 대해서 나오는 0의 값을 총 합하여 c[x]에 넣는다.

 

그 다음,

def func(x, b):
    if x !=0 and x % b == 0: return 1+func(x//b,b)
    else: return 0

 

만약 x가 b로 나누어진다면 앞서 설명한 것처럼 맨 뒤에 0이 존재하게 된다.

x가 12라면 맨 뒤에 0이 존재하므로 1 + func(6, 2)를 return하고,

x가 6이라면 맨 뒤에 0이 존재하므로 1 + func(3,2)를 return하고,

x가 3이라면 맨 뒤에 0이 존재하지 않으므로 return 0 을 한다. 그러면 x가 6일 때 return 1 + 0 이고,

x가 12일 때 1 + (1+0) 이므로 2를 return하게 된다.

 

for _ in range(int(input())):
    x = int(input())
    print(c[x])

그리고 알고자하는 값을 입력받아 c[x]로 반환하여 결과를 출력한다.