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

안녕하세요 평범한 컴공생입니다!

 

백준 1149번 문제 [RGB거리] 알고리즘 포스팅을 시작해보겠습니다.

전형적인 DP 문제인데, 처음에 DFS로 접근을 하려했다가 시간초과가 나서 DP로 방법을 바꾸니 해결할 수 있었습니다.

 

실버 1 난이도의 문제입니다.

1. 문제 해결 방법 구상하기

 - 빨간색으로 집을 칠하면 그 다음집은 파란색 또는 초록색으로밖에 칠할 수 없다.

 - 초록, 파랑의 경우도 마찬가지이다.

 - 두 번째 집에서 예를 들어 RED로 칠한다고 하면 첫 번째 집에서의 GREEN, BLUE를 선택한 값 중 더 작은 값에 RED를 칠했을 때의 값을 더한 것이다.

 - 세 번째 집에서 예를 들어 RED로 칠한다고 하면 두 번째 집을 BLUE로 했을 때 소요되는 최솟값과 GREEN로 했을 때의 최솟값 중에 더 작은 값에 RED로 칠했을 때의 값을 더한 것이다.

 - 일반화하여 dp 배열을 세워준다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

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

int N;
int price[1001][3];
int dp[1001][3] = { 0, };
int mincost = 987654321;

enum Color				// 열거형 사용으로 숫자를 색으로 표현가능
{
	COLOR_RED,			//RED 0
	COLOR_GREEN,		    	//GREEN 1
	COLOR_BLUE,			//BLUE 2
};

void input()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = COLOR_RED; j <= COLOR_BLUE; j++)
			cin >> price[i][j];
}

void solve()
{
	for (int i = 1; i <= N; i++)
	{
		dp[i][COLOR_RED] = min(dp[i - 1][COLOR_GREEN], dp[i - 1][COLOR_BLUE])+price[i][COLOR_RED];
		dp[i][COLOR_GREEN] = min(dp[i - 1][COLOR_RED], dp[i - 1][COLOR_BLUE])+price[i][COLOR_GREEN];
		dp[i][COLOR_BLUE] = min(dp[i - 1][COLOR_RED], dp[i - 1][COLOR_GREEN])+ price[i][COLOR_BLUE];
	}

	mincost = min(min(dp[N][COLOR_RED], dp[N][COLOR_GREEN]), dp[N][COLOR_BLUE]);
}

void output()
{
	cout << mincost << endl;
}

int main()
{
	input();
	solve();
	output();

	return 0;
}

확실히 dp 는 추상화하는 과정 자체가 어려운 것 같다. 하지만 계속 문제를 풀고 고민하고 다양한 문제를 접하다보니 dp 에 대해서도 감이 조금씩 잡히는 것 같다..!

 

/ /문제제기 및 피드백 언제든지 감사히 받겠습니다.