[BOJ] 백준 1149번 : RGB거리 (JAVA)

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

 

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

 

 

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

풀이

다이나믹 프로그래밍을 이용하여 해결할 수 있는 문제였습니다.

 

특정 집에 색깔을 칠할 때, 이전 집의 색과 겹치지 않게 칠하되, 최소의 비용을 구하는 것이 핵심이었습니다.

저는 위 문제를 Top-down 방식의 메모이제이션으로 풀었습니다.

 

첫 번째 집을 R, G, B로 칠하는 경우 각각에 대해서 메모이제이션을 수행한 다음, 첫 번째 집을 무슨 색으로 칠하는 것이 가장 작은 비용인지 구하시면 됩니다.

 

그리고 dp 배열을 아래와 같이 정의하고, 메모이제이션을 수행합니다.

 

 

dp[house][color] : 특정 집을 color 색으로 칠했을 때 드는 비용

 

 

메모이제이션 코드는 크게 어렵지 않으니, 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.