분할 정복 (1) 썸네일형 리스트형 [Python] 21870번 시철이가 사랑한 GCD https://www.acmicpc.net/problem/21870 24/11/04 단순한 분할정복 문제다. 문제 접근 방식: 얼핏 보면 시간제한이 1초고, 나이브하게 돌리면 빡빡할 것이라고 생각이 들 것이다. 우리는 왼쪽과 오른쪽으로 항상 배열이 나뉨을 관찰할 수 있다. 왼쪽 배열의 값들의 gcd + 오른쪽 배열의 최대 혹은 오른쪽 배열의 값들의 gcd + 왼쪽 배열의 최대 중 가장 큰 값이 우리가 원하는 값임을 확인할 수 있다. 오른쪽 배열의 최대 혹은 왼쪽 배열의 최대 또한 분할 정복을 통해 계속 재귀적으로 구할 수 있으므로, $\mathcal{O}(N \log N)$만에 문제를 해결할 수 있다. DP로 값을 저장하지 않아도 충분히 돌아감을 확인할 수 있다.(오히려 값을 저장하면 저장하는 시간때.. 이전 1 다음