-
[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. 코드 구현
1234567891011121314if __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