[BOJ][B2]Number Game- 1975

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

문제 전문은 링크 참조

문제가공

1. 숫자 N을 받는다.
2. 2진법,3진법..x진법으로 수를 변환한다.
3. 변환된 수의 끝자리의 연속된 0의 개수를 합친다. (ex: n진법으로 변환된수 = 103000200 일때, 끝자리 0의 개수는 2)

코드작성

단순하게 문제 그대로 모든 진수들의 끝자리를 반복해서 체크하면 시간초과로 테스트는 실패한다.

import sys
T = int(sys.stdin.readline())

def GetCountLastZero(val,base):  # 끝자리의 0 개수 확인하기
    result = 0
    while val%base== 0:
        result+=1
        val = val//base
    return result

for _ in range(T):
    answer = 0
    N = int(sys.stdin.readline())
    for base in range(2,N+1):
        answer += GetCountLastZero(N,base)
    print(answer)

속도와 효율성을 증가 시키기 위해 추가적인 규칙을 파악할 필요가 있다.

규칙파악

• N보다 높은 진수는 계산할 필요가 없다.

  ex) N = 10 이고 16진수를 계산한다고 가정했을 때,

  16진수에서 10= A로 표기된다.

  즉, 10보다 큰 x진수들은 N이 10단위의 수가 들어와도 10아닌 다른 형태의 문자로 표기를 해야 하기 때문.

• N의 약수들만 구해서 비교하면 된다.

  https://itbeginner2020.tistory.com/17

  진수를 변환하는 방법(위 링크 참조)은 해당 진수로 더 이상 나눌 수 없을 때 까지 계속 나누어,

  마지막 나눈 값과 그동안 나눠온 값들의 나머지를 반대로 읽으면 해당 진수로 변환이 된 것이다.

  정리하자면,

  입력된 N을 x진수로 변환하기 위해 x로 처음 나눈 값의 나머지가 x진수의 마지막 값이 된다.

  문제에서 요구하는 것은 마지막 자리의 연속된 0의 개수의 합이므로,

  애초에 나뉘어 지지않는 x진수는 계산할 필요가 없고,

  바꿔 말하면 N의 약수만 찾아서 계산하면 된다.

• 약수는 N의 제곱근 까지만 구하자.

  약수는 어느 한 수와 곱해져 N이 되는 값으로, 결국엔 어느 한 수도 N의 약수다.

  쌍을 이루는 약수 중 작은 수만 0의 개수를 계산하고, 큰 수는 0이 하나밖에 존재할 수 없으므로

  작은 수들의 0의 개수 + 작은 수들의 약수의 개수 가 답이 된다.

규칙을 적용한 코드는 아래와 같다.

import sys

T = int(sys.stdin.readline())

def GetCountLastZero(val,base): # 끝자리의 0 개수 확인하기
    result = 0
    while val%base== 0:
        result+=1
        val = val//base
    return result

def getTryNums(N): # 약수 구하기
    result = set()
    for i in range(1,int(N**0.5)+1):
        if N % i ==0:
            result.add(i)
            #result.add(N//i)
    return result


for _ in range(T):
    answer = 0
    N = int(sys.stdin.readline())
    arr = getTryNums(N) # 약수
    for base in arr : 
        if base == 1 : continue
        answer += GetCountLastZero(N,base)
    answer +=len(arr)- (1 if(N**0.5)%1 ==0 else 0)
    print(answer)