백준/1149번 :: RGB거리 (Python, 파이썬, 알고리즘)

 

문제

---

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

 

---

 

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

 

예제

---

예제입력

3
26 40 83
49 60 57
13 89 99

 

예제출력

96

 

코드

---

# -*- coding: utf-8 -*-
# Python 3.4.5
import sys

def solve(dp, n, cost) :
    for i in range(n) :
        if i == 0 :
            dp[i][0] = cost[i][0]
            dp[i][1] = cost[i][1]
            dp[i][2] = cost[i][2]
            continue
        # R
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        # G
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        # B
        dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])

    min_val = min(dp[n-1][0], dp[n-1][1])
    min_val = min(min_val, dp[n-1][2])
    return min_val

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    cost = []
    for _ in range(n) :
        temp = list(map(int, sys.stdin.readline().split()))
        cost.append(temp)
    dp = [[-1]*3 for _ in range(n)]
    print(solve(dp, n, cost))​

다이나믹 프로그래밍을 이용해서 풀었다.

 

처음에 R로 시작할때와 G로 시작할때, B로 시작할때로 3가지로 나눠서 계산을 한다. 처음값이 가장 작다고 결과값이 작은것은 아니기 때문이다.

 

결과

---

 

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

https://www.acmicpc.net/problem/1149