ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [D3] SWEA 17937. 큰 수의 최대공약수
    SWEA 2024. 4. 27. 22:37

    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. 코드 구현

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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}')
        
    cs

     

     

     

    4. 깨달은 점 및 반성

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

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

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

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

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

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

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

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

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

    'SWEA' 카테고리의 다른 글

    [D3] SWEA 17642. 최대 조작 횟수  (0) 2024.04.28
    [D3] SWEA 17319. 문자열문자열  (0) 2024.04.27
    [D3] SWEA 18662. 등차수열 만들기  (0) 2024.04.27
    [D3] SWEA 19003. 팰린드롬 문제  (0) 2024.04.27
    [D3] SWEA 19113. 식료품 가게  (0) 2024.04.27
Designed by Tistory.