백준 알고리즘 1149번: RGB거리(Python)

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

1149번: RGB거리

---

문제 해결을 위한 과정

이 문제 역시 전형적인 dp 즉 다이내믹 프로그래밍으로 해결할 수 있는 문제였습니다.

이해하기 쉽게 그림으로 그리면 다음과 같습니다. 간략하게 예시 1에 대해서 살펴봅시다.

먼저 3행 3열 이면서 int(1e9)으로 이루어진 이차원 리스트 dp는 다음과 같습니다.

 

그 후 0행에 예제의 정보들을 넣어주면 다음과 같습니다.

그 후 같은 열을 제외한 값을 더한 후 min값을 넣어주면 다음과 같습니다.

0행 1열에 대해서는 다음과 같습니다.

이러한 방식에 대해서 반복해나가면 쉽게 해결할 수 있습니다. 

---

소스코드 - python

n = int(input())
data = []
for _ in range(n):
  a, b, c = map(int, input().split())
  data.append((a, b, c))
 
dp = [[int(1e9)] * 3 for _ in range(n)]
a, b, c = data[0]
dp[0][0] = a; dp[0][1] = b; dp[0][2] = c
 
for i in range(n-1):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      else:
        dp[i+1][k] = min(dp[i+1][k], dp[i][j]+data[i+1][k])
 
print(min(dp[n-1]))

---

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
int main(void) {
  int n;
  scanf("%d", &n);
 
  int house[MAX][3];
  for(int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      scanf("%d", &house[i][j]);
    }
  }
 
  long long dp[MAX][3];
 
  fill(&dp[0][0], &dp[MAX-1][3], 1e9);
  dp[0][0] = house[0][0];
  dp[0][1] = house[0][1];
  dp[0][2] = house[0][2];
 
  for(int i = 0; i < n-1; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        if (j == k)
          continue;
        else
          dp[i+1][k] = min(dp[i+1][k], dp[i][j] + house[i+1][k]);
      }
    }
  }
 
  long long minValue = 1e9;
  for (int i = 0; i < 3; i++) {
    if(minValue > dp[n-1][i])
      minValue = dp[n-1][i];
  }
  printf("%lld", minValue);
  return 0;
}