구간 DP, 크누스 최적화
[1. 개요]구간 DP 크누스 최적화크누스 최적화는 구간 DP의 특정 조건을 만족할 때, 시간복잡도를 줄일 수 있는 방법최적 분할점은 단조롭게 증가한다는 성질을 이용한다.[2. 구간 DP]bottom-up[3. 크누스 최적화]아래와 같은 조건을 만족할 때 적용 가능하다.cost(a, c) + cost(b, d) # 사각 부등식# a # 구간이 겹칠 때 비용 합이, 큰 구간과 작은 구간의 비용합보다 크지 않아야 한다.cost(b, c) # a # 작은 구간의 비용이 큰 구간의 비용보다 크지 크지 않아야 한다.이 때, [i, j] 를 나누는 구간 k 를 설정하기 위해, [i, j] 를 탐색 범위로 잡는 것이 아니고,opt[i][j] ( 구간 [i, j] 를 최적으로 분할하는 위치 ) 를 k 라 할 때, k..
2485.
[1. 문제 설명]https://www.acmicpc.net/problem/2485[2. 풀이 접근]아래와 같은 생각이 들었는데간격이 제일 좁은 것 부터 1까지 줄이면서 배치하는 방식간격이 짝수, 홀수가 섞여있으면 모든 간격을 1로 배치 할 수 밖에 없음 등.여러 수들의 최대공약수를 구하면 위와 같이 복잡하게 생각할 것 없이 해결 가능하다. 최대 공약수 결합 법칙 gcd(a, b, c) = gcd(gcd(a, b), c)GCD의 본질은 "모든 수를 나눌 수 있는 최대 정수"gcd(a, b) = d 라 하면, d는 a와 b를 모두 나눌 수 있고,여기서 gcd(d, c) 를 구하면 결국 a, b, c 모두를 나누는 최대 정수가 된다.중간에 어떤 순서로 묶든 "모두를 나누는 최대 정수"라는 본질이 변하지 않..