[BOJ 5060] 무글 맵스

문제의 특성을 파악하기 위해 우선, 어떤 위치 i를 저장했다고 가정하자.

그러면 i를 기준으로 왼쪽과 오른쪽이 갈리게 된다.

왼쪽인 0 ~ i 번지의 오차를 계산할 때를 생각해 보면, 이미 i 가 저장되어 있기 때문에 i+1 ~ n-1 번지 중 어떤 위치가 저장되었는지는 상관이 없어진다.

다시 말해서 0 ~ i 번지와 i ~ n-1 번지 사이의 연결 고리는 ‘저장한 집이 몇 개인가’ 가 유일하게 된다. 이 것만 확정되면 나머지 요소들은 모두 독립적으로 작용한다.

그리고 이 정도 정보는 충분히 저장할 수 있기 때문에 다음과 같이 DP 문제를 정의해 볼 수 있다.

DP( i, j ) = 0 ~ i 번지의 집 중에 j 개를 저장했을 때 오차의 합의 최솟값

( 단, 0 과 i 번지는 반드시 저장 해야 함. )

이제 DP( i, j ) 를 구할 수 있는 하위 문제들과 관계식을 찾아야 한다.

이를 위해 i 번지 까지 j 개의 저장을 하는 모든 경우의 수를 생각해 보면, j 개를 저장하기 위해선 j-1개를 저장한 단계를 반드시 지나야 함을 알 수 있다.

이런 특징을 통해 하위문제를 DP( 0, j-1), DP( 1, j-1), … , DP( i-1, j-1) 로 설정할 수 있다.

이들 중 하나도 거치지 않고 DP( i, j ) 상태에 도달하는 것은 불가능하다.

이 점을 이용해 식을 정리하면 아래와 같이 된다.

DP( i, j ) = MIN ( DP( k, j-1) + error[k][i] ), k = 0 ~ i-1

( error[k][i] = k,i를 저장했을 때 그 사이 번지들의 오차의 합. )

답은 DP( n-1, c) / n 이 됨은 당연.

반복적 동적 계획법

재귀적 동적 계획법