1149) RGB거리 (C++)

출처 

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

1149번: RGB거리

 내 풀이 

#include<iostream>

using namespace std;

int house[1001][3];	//범위 지정 N=2~1000  RGB=3 
int N = 0;

int main()
{
	cin >> N;

	//RGB값을 입력받음 
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> house[i][j];
		}
	}

	//2부터 시작하여 전 값 비교
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			//만일 0(R일 경우) 전에 있던 G값과 B값을 비교하여 작은 값을 넣어준다. 
			if (j == 0)
			{
				house[i][j] = min(house[i][j] + house[i - 1][j + 1], house[i][j] + house[i - 1][j + 2]);
			}
			//만일 1(G일 경우) 전에 있던 R값과 B값을 비교하여 작은 값을 넣어준다.
			else if (j == 1)
			{
				house[i][j] = min(house[i][j] + house[i - 1][j - 1], house[i][j] + house[i - 1][j + 1]);
			}
			//만일 2(B일 경우) 전에 있던 R값과 G값을 비교하여 작은 값을 넣어준다. 
			else
			{
				house[i][j] = min(house[i][j] + house[i - 1][j - 2], house[i][j] + house[i - 1][j - 1]);
			}
		}
	}

	/* 잘 비교되었는지 확인 
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cout << house[i][j] << " ";
		}
		cout << endl;
	}
	*/

    //결과 초기값은 임의로 맨 마지막 N 0 배열에 있는 수 배치 
	int result = house[N][0];

	for (int i = 0; i < 3; i++)
	{
		result = min(result, house[N][i]);
	}
	cout << result;
}

 

 해설

맨 처음 지문이 이해가 안가서 동빈나님 다이나믹 프로그래밍 강의를 한번 더 들은 후 풀어보았다.

 

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

RGB 값을 입력 받고 2번째 RGB값부터 위의 조건에 따라서 

R -> 현재 R + 이전 G, 현재 R+ 이전 B

G -> 현재 G +이전 R, 현재 G + 이전 B

B -> 현재 B + 이전 R, 현재 B + 이전 G

2개값을 비교하여 최소값을 넣어가면서 마지막까지 반복해주었다. 

 

마지막 RGB값을 비교해서 작은 값을 출력하게 해주었다. 

 

 새로 안 것 

다이나믹 프로그래밍 하는 방법