[백준/C++] 1149 RGB거리 (S1)

유형	난이도	완료일	링크	특이사항
DP	실버1	23/02/19	https://www.acmicpc.net/problem/1149	오래 걸림

 

내 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int arr[1001][3];
int visited[1001][3];
int n;

int Recursion(int row, int column)
{
	if(row == n-1)
		return arr[row][column];
	
	if(visited[row][column]!=0)
		return visited[row][column];
	
	int a, b;
	
	if(column == 0)
	{
		a = Recursion(row+1, 1);
		b = Recursion(row+1, 2);
		if(a<b)
		{
			visited[row][column] = a + arr[row][column];
			return a + arr[row][column];
		}
		else
		{
			visited[row][column] = b + arr[row][column];
			return b + arr[row][column];	
		}
	}
	
	else if(column == 1)
	{
		a = Recursion(row+1, 0);
		b = Recursion(row+1, 2);
		if(a<b)
		{
			visited[row][column] = a + arr[row][column];
			return a + arr[row][column];
		}
		else
		{
			visited[row][column] = b + arr[row][column];
			return b + arr[row][column];	
		}		
	}
	
	else
	{
		a = Recursion(row+1, 0);
		b = Recursion(row+1, 1);
		if(a<b)
		{
			visited[row][column] = a + arr[row][column];
			return a + arr[row][column];
		}
		else
		{
			visited[row][column] = b + arr[row][column];
			return b + arr[row][column];	
		}		
	}
}

int main(void)
{
	cin >> n;
	
	
	for(int i = 0; i<n; i++)
	{
		for(int j= 0; j<3; j++)
		{
			cin >> arr[i][j];
		}
	}
	
	
	int A, B; // A = min
	int A_idx, B_idx;
	
	int first[3];
	first[0] = arr[0][0]; first[1] = arr[0][1]; first[2]=arr[0][2];
	
	sort(first, first+3);
	A = first[0]; B = first[1];
	
	for(int i=0;i<3;i++)
	{
		if(arr[0][i]==A)
			A_idx = i;
		if(arr[0][i]==B)
			B_idx = i;
	}
	
	int first1, sec1;
	
	first1 = Recursion(0, A_idx);
	if(A_idx == B_idx)
	{
		B_idx+=1;
		if(B_idx>2)
			B_idx-=2;
	}
	sec1 = Recursion(0, B_idx);
	
	//cout << A_idx << "\\n" << B_idx << "\\n";
	
	if(first1 < sec1)
		cout << first1;
	else
		cout << sec1;
		
}

중복되는 계산을 저장해두고 불러오는 아이디어 기반으로 코드를 짰다.

DFS방식으로 n-1번째 집까지 탐색하고, 끝에서부터 return 하면서 i번째 집의 R, G, B 색을 칠할 때 각각 최소 비용이 얼마인지 저장한다.

arr[n-1][2] = 80, arr[n-1][1] = 10 이라면 arr[n-2][0] = 5일 때, arr[n-2][0]을 칠했을 경우(n-2번째 집을 0번, 즉 빨강으로 칠함)의 최소합은 arr[n-1][1]+arr[n-2][0]인 15이다. 이후 i번째에 j색을 칠할 경우 추가되는 최소합을 저장하는 visited[1001][3]배열의 visited[n-2][0]에15를 저장한다. 이런 식으로 마지막(n-1번째)부터 값을 저장하면 중복되는 값이 있을 경우 다시 계산할 필요 없이 visited 배열에서 값을 불러올 수 있고 시간 내에 문제를 해결할 수 있다.

n-1번째 집을 칠할 때 최소합을 이용하여 n-2번째 집을 칠하는 최소합을 구하고, n-3번째 집을 칠하는 최소합을 구하고 , … 반복하여 1번째 집을 칠할 때 필요할 비용의 최소합까지 구한다. 1번째 집의 3가지 색 중 비용이 적은 순으로 2개만 선별하여 재귀함수를 돌리면 최소합의 가능성이 있는 모든 경우를 탐색할 수 있다.(1번째의 선택지 중 2개만 선택하면 2번째의 모든 선택지를 선택해볼 수 있으므로)

57%에서 틀렸다고 해서 봤더니 N=2이고 중복되는 숫자가 있는 입력에서 오류가 나는걸 발견했다.

for(int i=0;i<3;i++)
	{
		if(arr[0][i]==A)
			A_idx = i;
		if(arr[0][i]==B)
			B_idx = i;
	}

A와 B값이 같아 인덱스까지 같아지는 걸 방지하는 코드를 추가하여 통과할 수 있었다.

간결한 풀이

#include <iostream>
#include <algorithm>
using namespace std;
int house[1001][3];
int main() {
    int N;
    int cost[3];
    house[0][0] = 0;
    house[0][1] = 0;
    house[0][2] = 0;
    cin >> N;
    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][1],house[i-1][0]) + cost[2];
    }
    cout << min(house[N][2],min(house[N][0],house[N][1]));
}

현재의 집을 특정 색으로 칠할 때 이전 집의 색은 2개로 좁혀진다. 2개의 색 중 더 가중치가 낮은 집을 선택한다. [1001][3]크기의 배열에 각 단계별(i번째 집)로 해당 색을 칠할 때 필요한 최소의 비용을 저장한다. 내 코드와 반대로 맨 처음 집부터 필요한 비용을 저장해서 n번째가 되면 마지막 집의 해당 색을 칠하는데 필요한 최소 비용이 구해져 계산이 끝나는 방식이다.

모든 i번째 집들의 모든 색에 대하여 해당 색이 칠해지는데 필요한 최소 비용을 구하기.

모든 집의 모든 색이 각각 칠해지는데 얼마만큼의 최소 비용이 필요한지 구해볼 생각을 못했다. 생각해도 각 단계별로 최소 비용이 얼마일까 구해보려 했지 색 하나하나에 대해 최소 비용을 구하는 것은 생각을 못했다. 결국 내 코드와 비슷하지만, 나는 이런 개념을 가지고 코드를 짰다기 보다는 DFS로 생각하고 중복을 기록한다는 아이디어를 위주로 코드를 짜서 많이 달라진 것 같다.

역시 DP는 n번째를 구하기 위해 n-1번째를 이용하는 것이라고 다시금 느낀다. 물론 이걸 알고있어도 문제가 쉽게 풀리진 않는다. 그리고 DP는 항상 푼 문제도 글로 설명하기 유독 어려운 것 같다.