[BOJ] 1149 RGB거리 C++

개요

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

1149번: RGB거리

 

풀이

DP 문제 몇 개 풀다보니까 이정도는 이제 어느정도 보이는 것 같다.

현재 가격은 이전 누적 가격 중 가능한 가장 저렴한 가격 + 현재 집 가격이다.

3가지 색상의 가격을 비교하며 모든 집을 채워 넣다보면 마지막 3가지 경우 중 작은 값이 정답이 된다.

 

코드

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

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int N;
	int cost[3];
	int dpCost[1000][3];

	cin >> N;
	for (int j = 0; j < 3; j++)
	{
		cin >> cost[j];
		dpCost[0][j] = cost[j];
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
			cin >> cost[j];
		for (int j = 0; j < 3; j++)
		{
			int minCost = INT_MAX;
			for (int k = 0; k < 3; k++)
			{
				if (j == k) continue;
				minCost = min(minCost, cost[j] + dpCost[i - 1][k]);
			}
			dpCost[i][j] = minCost;
		}
	}
	int minDp = INT_MAX;
	for (int j = 0; j < 3; j++)
		minDp = min(minDp, dpCost[N - 1][j]);

	cout << minDp;
}

INT_MAX 사용시 climits를 include 해주어야 BOJ에서 컴파일 에러가 안난다,,