[백준] RGB거리 with C++

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

언어: C++, 시간: 0ms

 

접근방법

대표적인 dp를 이용하는 문제. 

먼저 입력을 행이 N이고 열이 3인 맵에 담고 난 후, 

0행부터 N-1행까지 dp로 최솟값의 합을 저장한다:

 

i 번째 행의 R칸에는 i-1번째의 G칸과 B칸 중 min을 저장한다.

i 번째 행의 G칸에는 i-1번째의 R칸과 B칸 중 min을 저장한다.

i 번째 행의 R칸에는 i-1번째의 R칸과 G칸 중 min을 저장한다.

.

.

.

이런식으로 저장하게 되면, i번째 행의 각 열에는 

i번째 집에 해당 색깔로 색칠했을때 + 그 이전 행들에 색칠하는 총 최소 비용이 저장된다.

dp를 다 구하고 난 후, 정답은 N-1 행의 각 열에 담긴 숫자 중 최솟값이다.

 

1000 x 1000은 int 범위 내이므로 int로 풀어도 충분하다.

 

잘 이용하면 코드를 좀 더 줄일 수도 있다!

최종코드

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int MAP[1000][3];

int main() {

	// 입력받기
	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < 3; j++){
			cin >> MAP[i][j];
		}
	}

	// dp로 합 저장하면서 수행
	for (int i = 1; i < N; i++){
		int preCostSumR = MAP[i - 1][0];
		int preCostSumG = MAP[i - 1][1];
		int preCostSumB = MAP[i - 1][2];
		MAP[i][0] = MAP[i][0] + min(preCostSumG, preCostSumB);
		MAP[i][1] = MAP[i][1] + min(preCostSumR, preCostSumB);
		MAP[i][2] = MAP[i][2] + min(preCostSumR, preCostSumG);
	}

	cout << min({ MAP[N-1][0], MAP[N - 1][1], MAP[N - 1][2] });

	return 0;
}