BaekJoon 1149번: RGB거리

풀이법

1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다.

    단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다.

    나올 수 있는 경우의 수를 구현하되 DP의 메모이제이션을 활용하여 시간 제한인 0.5초의 벽을 뚫는 것이 핵심이다.

   

    arr[i][0] : i번째 집을 빨간색으로 칠하는 비용

    arr[i][1] : i번째 집을 초록색으로 칠하는 비용

    arr[i][2] : i번째 집을 파란색으로 칠하는 비용

 

    ans[i][0] : i번째 집을 빨간색으로 칠했을 때까지의 최소비용

    ans[i][1] : i번째 집을 초록색으로 칠했을 때까지의 최소비용

    ans[i][2] : i번째 집을 파란색으로 칠했을 때까지의 최소비용

  

    해당 배열을 이용하여 재귀 식을 만들면 다음과 같다.

  

    ans[i][0] = min(ans[i - 1][1], ans[i - 1][2]) + arr[i][0];
    ans[i][1] = min(ans[i - 1][0], ans[i - 1][2]) + arr[i][1];
    ans[i][2] = min(ans[i - 1][0], ans[i - 1][1]) + arr[i][2];

    

    최종 값 : min(ans[n][0], min(ans[n][1], ans[n][2]));

 

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

int n;
int arr[1001][3];
int ans[1001][3];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			int a;
			cin >> a;
			arr[i][j] = a;
		}
	}
	ans[0][0] = 0;
	ans[0][1] = 0;
	ans[0][2] = 0;
	for (int i = 1; i <= n; i++)
	{
		ans[i][0] = min(ans[i - 1][1], ans[i - 1][2]) + arr[i][0];
		ans[i][1] = min(ans[i - 1][0], ans[i - 1][2]) + arr[i][1];
		ans[i][2] = min(ans[i - 1][0], ans[i - 1][1]) + arr[i][2];
	}
	cout << min(ans[n][0], min(ans[n][1], ans[n][2]));
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest