백준 1149번 RGB거리

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
using namespace std;

int n;
int rgb[1001][3];// [k번 집][k번 집 색]에서의 색칠 비용
int dp[1001][3]; // [k번 집][k번 집 색]에서의 최소비용

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
}


void SOLVE()
{
	// 초기 설정
	dp[1][0] = rgb[1][0]; dp[1][1] = rgb[1][1]; dp[1][2] = rgb[1][2];

	// Bottom Up Dynamic Programming
	/*
	* 차례대로 집을 순회하며, i번색에서 j번색으로 갔을때의 최소 색칠비용을 갱신한다.
	* n번 집까지 계산한 후, 색깔별 값 중 최소값이 곧 최소 비용이므로 출력한다.
	* 
	*  // 이렇게 풀고나니, 아예 입력받으면서 [k번 집][색]까지의 최소비용을 구한 후,
	*  // 출력만 했어도 훨씬 쉽고 깔끔하게 풀 수 있음을 알았다..
	*/
	for (int home = 2; home <= n; home++)
	{
		for (int i = 0; i < 3; i++) // home - 1번 집 색
			for (int j = 0; j < 3; j++) // home번 집 색
			{
				if (i == j) continue; // 이전 집과 색이 달라야함

				// dp값이 존재하지 않는다면, dp[이전 집][i번색] + rgb[현재 집][j번색]
				if (!dp[home][j]) dp[home][j] = dp[home - 1][i] + rgb[home][j];
				// dp값이 존재한다면, 기존값과 dp[이전 집][i번색] + rgb[현재 집][j번색] 중 작은 값
				else dp[home][j] = min(dp[home][j], dp[home - 1][i] + rgb[home][j]);
			}
	}
	cout << min(dp[n][0], min(dp[n][1], dp[n][2]));
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.