[SWEA] 5688. 세제곱근을 찾아라(python)

문제

양의 정수 N에 대해N = X^{3}가 되는 양의 정수 X를 구하여라.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1\leq N < 10^{18})이 주어진다.

 

출력

각 테스트 케이스마다 첫 번째 줄에는‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다.)를 출력하고, N = X^{3}가 되는 양의 정수 X를 출력한다.

만약 이런 X가 존재하지 않으면 -1을 출력한다.

 

문제 풀이

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    x = N ** (1/3)
    num = int(x)
    
    if x + 0.01 >= num + 1:
        answer = int(x + 0.1)
        
    elif x < 0 or N % x != 0:
        answer = -1
        
    else:
        answer = x
        
    print(f'#{tc} {int(answer)}')

x를 N의 세제곱근으로 구했을 때, 1/3이 float가 되어 나누어 떨어지지 않는 문제가 발생했다.

3.9999...나 6.9999..로 수렴하는 수 일 경우, 각각 수렴하는 수로 구하기 위해서

구하고 싶은 수 = int로 정수로 만들어 준 숫자에 1을 더한 숫자

비교할 숫자 = 세제곱근으로 구해진 숫자 x + 0.01

비교할 숫자가 구하고 싶은 수보다 크다면, 수렴하는 수라고 가정하고 답을 int(x + 0.1)로 구해주었다.

 

 

 

다른풀이

이러한 문제를 풀 때 정석 풀이는 이진탐색이라고 짝꿍분이 알려주셨다.

def binary_search(target,start,end):
     
    while start <= end:
         
        mid = (start+end)//2
 
        if mid**3 == target:
             
            return mid
         
        elif mid**3 > target:
             
            end = mid-1
         
        else:
             
            start = mid+1
     
    return -1
 
T = int(input())
 
for t in range(1,T+1):
     
    target = int(input())
 
    print('#'+str(t),binary_search(target,0,target))

더 공부해서 이진탐색으로도 풀어봐야겠다!

 

추천 풀이 문제

BOJ ▶️ # 3783 # 2731 # 4690