문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
코드
#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 }); } |
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)); } } } |
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)) |
복기
점화식은 도출했는데 구현을 잘못된 방향으로 하고 있었다. 다음에는 주의해야겠다.