티스토리 뷰

문제 풀이

[BOJ 5060] 무글 맵스

RiKang 2017. 10. 31. 17:20

문제의 특성을 파악하기 위해 우선, 어떤 위치 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 이 됨은 당연.


반복적 동적 계획법


재귀적 동적 계획법


'문제 풀이' 카테고리의 다른 글

[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31
[BOJ 5060] 무글 맵스  (0) 2017.10.31
[BOJ 2057] 계단 오르기  (0) 2017.10.31