반응형
https://www.acmicpc.net/problem/1149
1149번: RGB거리
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
DP 점화식을 세워서 해결할 수 있는 문제.
각 집마다 R, G, B 색깔로 칠할 때의 비용이 주어지므로, idx 0 = R, 1 = G, 2 = B로 정의하면
0 <= j < 3인 j에서
dp[i][j] = i번째 집을 idx j 색깔로 칠할 때 드는 비용.
dp[i][j] = min(dp[i-1][j+1 % 3], dp[i-1][j+2%3]) + 해당 집을 idx j로 칠할 때의 비용)
즉, 현재 위치 직전의 집 중에서 현재 선택한 색깔을 제외한 나머지 색깔 중 최솟값 + 현재 위치에서 현재 색깔로 칠할 때의 비용을 계산한다.
이렇게 되면, dp[-1]에서 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 14501. 퇴사 (0) | 2019.12.31 |
|---|---|
| [Python] 백준 1939. 중량제한 (0) | 2019.12.30 |
| [Python] 프로그래머스. 가장 큰 정사각형 (Level 2) (0) | 2019.12.26 |
| [Python] 프로그래머스. 구명 보트 (Level 2) (0) | 2019.12.25 |
| [Python] 백준 2655. 가장 높은 탑 쌓기 (0) | 2019.12.24 |