[BOJ/python] 1149번 RGB거리

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

1149번: RGB거리

문제 해석

 

처음 문제해석때 이해가 안가서 좀 애먹었다.. RGB를 사용한 하나의 색인줄 알았는데 R, G, B 중 하나를 골라 칠하는 것이다. 즉, 1번집이 빨강이면 2번집은 초록이나 파란색이여야 한다. 이를 반복하여 모든 집을 칠하는 최소 비용을 출력해야 한다.

---

코드

 

# BOJ 1194

# input
n = int(input())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))


dp = [[0] * 3 for _ in range(n)]
# 첫 시작 값 채워주기
for i in range(3):
	dp[0][i] = arr[0][i]

# 값을 채울때는 i-1에 있는 같은 위치를 제외한 두 값 중 최소값을 더해서 채우기
for i in range(1, n):
	for j in range(3):
		dp[i][j] = min(dp[i-1][(j+1) % 3] + arr[i][j], dp[i-1][(j+2) % 3] + arr[i][j])

print(min(dp[-1]))

---

문제 풀이

 

이 문제는 대표적인 DP문제이다. 따라서 조건에 따라 적어가면서 규칙을 찾아내는것이 좋다.

첫 dp의 값은 항상 고정이다. 각각 R, G, B를 먼저 칠했을 경우이다.

다음이 최소 비용이 되도록 하려면 두번째 행에 위치한 자신과 같은 열에 존재하지 않는 값의 최소 값을 더해주어야 한다.

즉, 60 과 57 중에서 57의 값이 적으므로 26 + 57값이 빨간 점선의 네모칸에 오게된다.

 

이 규칙을 반복하여 구현하면 쉽게 풀 수 있다.