[백준] 1149번 RGB거리 / C++

#문제

백준 1149번 RGB거리

#풀이

#include <iostream>
#include <algorithm>

#define MAX 1002
using namespace std;

int house[MAX][3];

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	int cost[3];
	house[0][0] = 0;
	house[0][1] = 0;
	house[0][2] = 0;

	for (int i = 1; i <= N; ++i)
	{
		cin >> cost[0] >> cost[1] >> cost[2];

		house[i][0] = min(house[i - 1][1], house[i - 1][2]) + cost[0];
		house[i][1] = min(house[i - 1][0], house[i - 1][2]) + cost[1];
		house[i][2] = min(house[i - 1][0], house[i - 1][1]) + cost[2];
	}

	cout << min(min(house[N][0], house[N][1]), house[N][2]);
}

#정리

칠하려는 집의 색상이 이전, 이후 집과 중복되지 않으면서, 모든 값을 구했을 때 최소의 값을 구하는 문제다. dp를 이해하고, 사용할 줄 안다면 쉽게 풀 수 있다.




    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • [백준] 1037번 최소공배수 / C++
  • [백준] 11650번 좌표 정렬하기 / C++
  • [백준] 1934번 최소공배수 / C++
  • [백준] 1940번 주몽 / C++
  • [백준] 1010번 다리 놓기 / C++