[D3] SWEA 17937. 큰 수의 최대공약수

D3 문제 중 유일하게 풀지 못했다.

1<=A<=B<=10100의 조건을 보고

정석적으로 접근했었다.

1부터 A의 약수를 구한 뒤

A+1~B까지 A의 약수 리스트에 있는 수로 나눠지는 수 중

가장 큰 수 이런 식으로 구할려했다.

1. 접근 방식

문제의 조건 중 10100=10^100이었다.

시간복잡도가 어마어마할 것이다.

정석적으로 접근하면 안된다는 사실을 알 수 있다.

 

이 사실을 알 수 있다.

자신이랑 1 차이가 나는 숫자와의 최대공약수는 항상 1이다.

ex) gcd(2,3)=1, gcd(3,4)=1, gcd(55,56)=1, gcd(24,25)=1 , ~~~

->이렇게 자신이랑 1 차이가 나는 숫자와의 최대공약수가 항상 1이면

    뒤를 따지는 것은 의미가 없다.

 

2. 디테일한 구현

1) a==b

최대공약수 a(b)

 

2)a<b

최대공약수 1

 

 

3. 코드 구현

if __name__=='__main__':
    sys.stdin=open('input2.txt','r')   
    
    
    t=int(input()) ## 총 테스트 케이스 개수
    
    for tc in range(t):
       a,b=map(int,input().split())
       
       if a==b:
           print(f'#{tc+1} {a}')
       elif a<b:
           print(f'#{tc+1} {1}')
    

 

 

 

4. 깨달은 점 및 반성

문제 풀이 실패 이유는 2가지가 있다.

1)나는 인접한 두 수 사이의 최대공약수는 항상 1이다.라는

사실이 수학적으로 증명이 돼?

이렇게 빡빡하게 생각하는 버릇이 있어서다.

하지만 D3이고 그렇게 빡빡한 생각을 요구하지는 않는 것 같다.

좀 더 널널하게, 편하게 생각하자.

2)조건이 작은 것부터 큰 것까지 나열하게 생각하지 않았다.

->수열의 길이가 1,2,3,~~n개 이런 식으로 확장하는 버릇을 들여야한다.

->추상적으로 생각하는 버릇이 있다.