백준 1149번 "RGB" 거리 (Dynamic Programming)

문제 설명

문제 설명

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 순서.

 

1. 문제를 보면 경우의 수가 여러가지인 경우인 문제이다. 

    처음에는 각 집마다 색을 선택하는 경우가 2가지씩 생기므로 계속해서 완전 탐색한다면 ( 2^n) 복잡도

    경우의 수가 기하급수적으로 증가하게 되므로 이 문제에 옳치 않은 풀이 방법이라 생각했습니다.

 

2.  따라서 이전의 결과값을 저장하고 재활용하는 Dynamic Programming을 사용하여 

     각 집을 특정 색으로 칠했을 때의 최소 비용을 누적해서 구하는 방식으로 해결하기로 생각했습니다.

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

코드 결과

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 

int main()
{
	int i_inputCount = 0;
	cin >> i_inputCount; 

	
	int dp[1001][3] = { 0, };

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

	
	int result = min(dp[i_inputCount][0], min(dp[i_inputCount][1], dp[i_inputCount][2]));

	cout << result;

	

	return 0;
}