[BOJ] 1149번 RGB거리

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

코드

• C++ 17

#include <iostream> #include <algorithm>   using namespace std;   int N;   // 현재 RGB 비용 int R, G, B;   // 이전 RGB 비용 int r, g, b;   int main() {     ios::sync_with_stdio(false);     cout.tie(nullptr);     cout.tie(nullptr);       cin >> N;     for (int i = 0; i < N; ++i)     {         cin >> R >> G >> B;                  // 최소값을 구해야하므로 메모이제이션 해야할 값은 최소값이다.         // 이웃끼리 같은 색깔을 쓸 수 없으므로         // 하나의 색깔이 정해지면 그 다음 색깔도 정해진다.         // 이 특성을 바탕으로 하나의 색깔에 대한 점화식은 다음과 같다.         // Dp(N, R) = Cost(R) + Min(Dp(N - 1, G), Dp(N - 1, B))         // 다른 색깔에 대해서도 마찬가지이다.         R += min(g, b);         G += min(r, b);         B += min(r, g);                  // 업데이트한다.         r = R;         g = G;         b = B;     }          // 그 중 가장 작은 값을 택하면 된다.     cout << min({ r, g, b }); }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static int N;         static int R, G, B;         static int r, g, b;           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             for (int i = 0; i < N; ++i)             {                 string[] inputs = Console.ReadLine().Split();                 R = Convert.ToInt32(inputs[0]);                 G = Convert.ToInt32(inputs[1]);                 B = Convert.ToInt32(inputs[2]);                   R += Math.Min(g, b);                 G += Math.Min(r, b);                 B += Math.Min(r, g);                   r = R;                 g = G;                 b = B;             }               Console.Write(Math.Min(Math.Min(r, g), b));         }     } }

• Python 3

N = int(input()) r, g, b = 0, 0, 0   for i in range(N):     R, G, B = map(int, input().split())       R += min(g, b)     G += min(r, b)     B += min(r, g)       r, g, b = R, G, B   print(min(r, g, b))

복기

점화식은 도출했는데 구현을 잘못된 방향으로 하고 있었다. 다음에는 주의해야겠다.