개발 · 컴퓨터공학/알고리즘
백준 14252 공약수열 파이썬 문제풀이 (python 정수론 최적화)
문제 보러가기 백준 공약수열 파이썬 문제풀이공약수 gcd 기법을 이용하는 문제이지만 상당히 어려운 문제이다. 주어진 수들을 나열했을 때 인접 두 수가 서로소가 되도록 중간에 수를 추가하는데, 몇 개를 추가해야하는지 구하는 문제이다. 중간에 들어가는 수가 반드시 하나라는 법이 없기 때문에 서로 비교하는 방법이 헷갈린다. 우선 단순히 접근해서 로직을 만들었다. 인접한 두 수 a,b가 있고 그 사이에 들어가는 수를 c라고 한다. gcd(a,b) == 1이면 넣으면 되고, 그게 아니라면gcd(a,c) == 1이면서 gcd(c,b) == 1인 값을 찾는다.없다면 gcd(a,c) == 1만 만족하는 수를 넣고 gcd(d,b)를 시도한다. 이 로직을 염두하고 코드를 짜보자.def gcd(a,b): while ..
2024. 9. 19. 11:34
