목록Dynamic Programming (1)

태코놀로지

DP 문제풀이 #2 - RGB 거리

첫 번째 문제에 이어서 선택한 문제는 백준 온라인 저지의 1149번 문제가 되겠다. 이웃과 서로 다른 색깔의 페인트로 집을 칠할 때, 가능한 초소의 비용을 찾는 문제다. 색은 R, G, B로 한정되어 있으며, 집의 수는 사용자의 입력으로 결정된다. 예를 들면, 아래와 같은 경우를 생각해볼 수 있다. R G B집1| 26 40 83집2| 49 60 57집3| 13 89 99 이 경우의 최소의 값은 (집1-R, 집2-B, 집3-R)로 색칠하는 방법으로 최소비용 96이 답안이 된다. 그리디 알고리즘이나 다른 방법을 통해서도 문제를 풀 수 있겠지만, Overlapping SubProblem 구조와 Optimal Substructure 특징이 두드러지는 문제이므로 다이나믹 프로그래밍을 활용하면 쉽게 해결할 수 있..
Algorithm/Dynamic Programming 2017. 2. 5. 16:32
Prev 1 Next