[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 색으로 칠했을 때 드는 비용
메모이제이션 코드는 크게 어렵지 않으니, 아래 소스코드를 참고하시길 바랍니다.
소스코드
지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.
'PS > 백준' 카테고리의 다른 글
[BOJ] 백준 2302번 : 극장 좌석 (JAVA) (0) | 2020.09.13 |
---|---|
[BOJ] 백준 10826번 : 피보나치 수 4 (JAVA) (0) | 2020.09.11 |
[BOJ] 백준 2636번 : 치즈 (JAVA) (0) | 2020.09.08 |
[BOJ] 백준 1495번 : 기타리스트 (JAVA) (0) | 2020.09.07 |
[BOJ] 백준 5557번 : 1학년 (JAVA) (0) | 2020.09.06 |
댓글