[D3] SWEA 16800. 구구단 걷기

1. 접근 방식

문제의 조건을 보자.

(2 <= N <= 10^12) 

10^12은 굉장히 큰 값이다.

따라서, 탐색하는 변수를 대폭 줄이는 방법을 발견해야한다.

나는, 이 방법을 찾지 못해서 문제 풀이에 실패했다.

 

2. 디테일한 구현

24=(1,24),(2,12),(3,8),(4,6)   대칭   (6,4),(8,3),(2,12),(24,1)

36=(1,36),(2,18),(3,12),(4,9) (6,6) (9,4),(12,3),(18,2),(36,1)

 

이렇게 탐색 구간을 1~n이 아니라 1~int(math.sqrt(n))으로 바꿔주면

10^12은 10^6이 되면서 대폭 줄여지게 된다.

 

3. 코드 구현

import math
 
if __name__=='__main__':
    #sys.stdin=open('input2.txt','r')   
    
    
    t=int(input()) ## 총 테스트 케이스 개수
    
    for tc in range(t):
       n=int(input())
       half_n=int(math.sqrt(n))
      
       res=float('inf')
       for i in range(1,half_n+1):
           if n%i==0:
               if res> i+(n//i)-2:
                   res=i+(n//i)-2
               
 
       print(f'#{tc+1} {res}')

 

 

 

4. 깨달은 점 및 반성

n=2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 까지

일일이 나열해봤지만 문제 풀이 해법을 발견하지 못했다.

10^12의 숫자에 압도당해서 어떠한 넌센스적인

풀이 방법이겠구나 생각했구나

정석+탐색 범위 줄이기였다.

정석에 집중하면서 쫄지 말자