백준 2731 python

문제 링크

문제 설명

좀 쓰기 난해했던 벡트래킹 문제.

구하는 것은 1,3,7,9로 시작하는 숫자 num1을 주었을 때 임의의 수 num2를 세제곱해서 num2**3의 가장 아랫자리 숫자가 num1이 되게 하는 num2를 구하는 문제였다.

예를 들어 input에 53이라는 숫자가 들어갈 경우
return값은 37을 뽑아주면 된다.(37**3 == 50653이고 이 숫자는53으로 시작하기 때문이다.)

1. 1,3,7,9로 시작하는 수를 세제곱하면서 얻는 첫 번째 자리 수가 유일하게 각각 1,7,3,9라는 것을 찾을 수 있었고(이경우 반드시 필요한 조건은 아니다.),
2. input으로 주어지는 숫자가 10자리 이하라는 것(이말은 결과적으로 각각의 case에 대해 그 결과가 항상 10자리 이하의 숫자가 될 수 있다는 것과 동일하다.) 때문에 플레5 문제임에도 불구하고 시간복잡도를 고려하지 않아도 되겠는데? 하면서 코드 구현에만 집중할 수 있었다.

input과 output은 다음과 같다.
input의 첫 번째 줄은 test case의 갯수 T이고, 그 다음 T개의 줄에는 test case의 숫자가 들어간다.
output에는 위에 설명한 조건을 충족하는 각각의 test case에 대한 T개의 숫자를 출력해주면 된다.

결과 코드

from sys import stdin

def get_num(num_lst,last_num,idx):
    if str(int(''.join(num_lst[::-1]))**3)[::-1].startswith(last_num):
        return True,num_lst
    
    for i in range(10):
        result_num = str(int(str(i) + ''.join(num_lst[::-1]))**3)[::-1]
        if result_num.startswith(last_num[:idx]):
            num_lst.append(str(i))
            return False,num_lst

case = int(stdin.readline().strip())

for _ in range(case):
    last_num = stdin.readline().strip()[::-1]
    first = int(last_num[0])
    num_lst = [str(10-first) if 2<first<8 else str(first)]
    
    idx = 2
    while True:
        check,num_lst = get_num(num_lst,last_num,idx)
        
        if check:
            print(''.join(num_lst[::-1]))
            break
            
        idx += 1

어떻게 계산하면 좋을까? 하다가 string을 막 뒤집는 케이스가 많아져가지고 보는 것은 좀 더러운 편이다..(굳이 정리하기는 귀찮..)

2번 아이디어의 이유

간단한 이유임에도 보통 빠르게 캐치가 안되는 계산문제여서 조금 적어보고자 한다. 낮은 자리수가 같은 몇개의 수를 제곱한다고 가정했을 때 그 제곱수의 끝자리를 비교해본다면 공통된 낮은 자리수의 길이만큼은 항상 동일하다. 또한 이는 어떤 제곱에서도 같은 원리가 유지된다.

간단한 예시를 하나 적어놓아본다.

'낮은 자리 수 예시 : 373'
print(16373**3)     # == 4389194087117
print(7777373**3)   # == 470434088733821594117
print(124362373**3) # == 1923388438207817369989117
'세 숫자 모두 낮은 자리 수가 117로 동일하고, 이는 373의 길이와 일치한다.'