[백준/Python] 1149 RGB거리

 

📌 문제 탐색하기

집의 개수 N (2 ≤ N ≤ 1,000)
선분 위에 N개의 집이 1번부터 N번까지 순서대로 있음
 
각 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 함
각 집마다 빨강, 초록, 파랑으로 칠하는 비용이 각각 다름
각 집은 이웃집과 색이 같지 않아야 함

모든 집을 칠하는 비용의 최솟값 구하기

 

알고리즘 선택하기

이 문제에서 확인할 수 있는 부분은 각 집의 색칠 비용은 이전 집의 색칠에 영향을 받는다는 것이다. 즉, i번째 집의 색칠 비용은 i+1번째 집의 색칠 비용과 연결되어 있다. i번 째 집을 빨강으로 칠하면, i+1번째 집은 초록 또는 파랑일 때의 최소 비용을 고려해야 한다.

각 집의 색칠 비용을 계산하고 저장하여 다음 집의 최소 색칠 비용을 결정해야 하므로 DP를 사용하는 것이 적합하다.

 

점화식 세우기

• dp[i][color] -> i번째 집을 color색(0: 빨강, 1:초록, 2:파랑)으로 칠했을 때의 1번째부터 i번째 집까지 칠하는 최소 비용
• dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + color_cost[i][0]
• dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + color_cost[i][1]
• dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + color_cost[i][2]

 

---

📌 코드 설계하기

1. 집의 개수(N) 입력 받기
2. 각 집을 빨강, 초록, 파랑으로 색칠할 때의 비용 2차원 리스트(color_cost)에 저장하기
3. 3xN 크기의 이차원 dp 리스트 생성
4. dp[0]은 color_cost[0]에 따라 초기화하기
5. 점화식에 따라 dp 리스트 채우기
6. min(dp[n-1]) 출력하기

 

---

📌 정답코드

N = int(input())
color_cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = color_cost[0]

for i in range(1, N):
  dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + color_cost[i][0]
  dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + color_cost[i][1]
  dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + color_cost[i][2]

print(min(dp[N-1]))