[BOJ] 백준 1149 RGB거리 (C++)

알고리즘 문제 풀이

문제

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

1149번: RGB거리

---

풀이

기본적으로 DP 다이나믹 프로그래밍 방식을 사용하는 문제인 것 같다.

배열에 RGB값을 각각 입력받고 DP 배열에다 RGB마다 최소값을 계산해서 저장해두는 방식을 사용했다.

i번째를 찾기 위해서 나름의 점화식?을 세워보았는데 밑의 3개의 식 중 최소값을 찾아서 출력하는 방식을 사용했다.

dp[i][0] = arr[i][0] + min(dp[i-1][1], dp[i - 1][2]);
dp[i][1] = arr[i][1] + min(dp[i-1][2], dp[i - 1][0]);
dp[i][2] = arr[i][2] + min(dp[i-1][1], dp[i - 1][0]);

---

소스 코드

#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

using namespace std;

int N;
int arr[1001][3];
int dp[1001][3];

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i][0];
		cin >> arr[i][1];
		cin >> arr[i][2];
	}
	
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];

	for (int i = 1; i < N; i++) {
		dp[i][0] = arr[i][0] + min(dp[i-1][1], dp[i - 1][2]);
		dp[i][1] = arr[i][1] + min(dp[i-1][2], dp[i - 1][0]);
		dp[i][2] = arr[i][2] + min(dp[i-1][1], dp[i - 1][0]);
	}

	cout << min(min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]) << '\n';
}

---