< 백준 BaekJoon : 1149번 RGB거리 > C++

<< 문제 >>

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

1149번: RGB거리

 

사실 DP를 이용하는 문제라는 것을 알고 풀기 시작해서 어떻게 사용할 수 있을지부터 고민했습니다. 

 

풀이방법은 뒤에서 부터 최소값을 구해오는 방식입니다. 

 

 

맨 뒤부터 각 자리를 기준으로 최솟값을 찾아갑니다. 

 

47 25 29는 뒷 줄에서 자신이 선택할 수 있는 색 중 최소값을 찾아 가져옵니다. 

그러면 66 44 89가 되고, 65 13 15는 이 중 자신이 고를 수 있는 최소값으로 65,15 -> 44    13 -> 66 으로 109 79 59가 됩니다. 

 

이런 방식으로 진행하면 됩니다. 

 

<< 코드 >>

#include <iostream>
using namespace std;

int sum[1000][3];

int main() {

	int num;
	cin >> num;

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < 3; j++) {
			int temp;
			cin >> temp;
			sum[i][j] = temp;
		}
	}

	// 뒤에서 부터 채워가는 방식
	for (int i = num - 2; i >= 0; i--) {
		for (int j = 0; j < 3; j++) {
			if (sum[i + 1][(j + 1) % 3] > sum[i + 1][(j + 2) % 3]) {
				sum[i][j] += sum[i+1][(j + 2) % 3];
			}
			else {
				sum[i][j] += sum[i + 1][(j + 1) % 3];
			}
		}
	}

	int min = sum[0][0];
	for (int i = 1; i < 3; i++) {
		if (sum[0][i] < min) {
			min = sum[0][i];
		}
	}

	cout << min;
}

 

 

<< 깃헙 >> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1149.%E2%80%85RGB%EA%B1%B0%EB%A6%AC