[Python] BOJ 1149 - RGB거리

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

1149번: RGB거리

2차원 DP배열을 사용하는 문제이다.

 

1. house를 입력받고, house크기만큼 dp배열을 선언해준다.

 

2. N == 1일때는 세 집중 최솟값을 그냥 출력하면 된다.

 

3. N이 2이상일때 DP테이블을 갱신하는 과정은 다음과 같다.

   dp[i][0]: 그 이전의 i-1번째에서 house[i-1][1]이나 house[i-1][2]를 선택한 경우 중 최솟값 

                      + 현재 i번째에서 0번째 색깔을 고른경우(house[i][0])

   dp[i][1]: 그 이전의 i-1번째에서 house[i-1][0]이나 house[i-1][2]를 선택한 경우 중 최솟값

                      + 현재 i번째에서 1번째 색깔을 고른경우(house[i][1])

   dp[i][2]: 그 이전의 i-1번째에서 house[i-1][0]이나 house[i-1][1]를 선택한 경우 중 최솟값

                      + 현재 i번째에서 2번째 색깔을 고른경우(house[i][2])

 

4. 이렇게 2번째 집부터 N번째 집까지 dp[i]를 갱신해주고 마지막에

   dp[N-1][0], dp[N-1][1], dp[N-1][2] 중 최솟값을 출력해주면 된다.

 

N = int(input())
house = []
dp = [[0] * 3 for _ in range(N)]
for _ in range(N):
	house.append(list(map(int,input().split())))
if N == 1:
	print(min(house[0][0], house[0][1], house[0][2]))
else:
	dp[0][0], dp[0][1], dp[0][2] = house[0][0], house[0][1], house[0][2]
	for i in range(1, N):
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0]
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1]
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2]
	print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))

(solved.ac 티어: 실버 1)