[DP] BOJ 1149번 RGB거리 - 오답노트

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

1149번: RGB거리

- 문제 파악

정수 n 과 n * 3 의 배열이 주어진다. 이전에 사용했던 배열의 위치를 사용하지 않는 배열의 합 중 최소값을 구하라.

 

- 나의 접근

2^n * 3 의 알고리즘 밖에 떠오르지 않고 아래와 같은 반례 때문에 간단한 문제임에도 쉽게 풀어내지 못했다.

 

내가 생각한 반례

3

1 2 100

100 100 100

1 1 1

 

최소값을 선택해서 나아간다는 단순한 알고리즘으로는 위와 같은 반례는 풀어낼 수 없었다.

그래서 모든 값을 봐야한다 생각했더니 2^n * 3이 떠올랐지만 시간 제한은 0.5초 무조건 시간 초과다.

 

- 정답

위와 비슷한 접근이지만 좀 더 무식하게 접근했으면 됐다.

 

일단 첫번째 원소에서는 최소값을 생각할 필요없이 무조건 칠한다고 생각하자.

하지만 그 다음부터는 문제의 조건때문에 첫번째 원소에서 선택한 위치의 원소는 사용할 수 없으므로 그 외 원소 중 가장 작은 값을 더해 나간다.

 

큰 문제를 작은 문제로 바꾸어 생각해야하는데 그게 어렵다;

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[1001][4];
int arr[1001][4];

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

	cin >> n;

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

	}

	D[0][0] = arr[0][0];
	D[0][1] = arr[0][1];
	D[0][2] = arr[0][2];
	
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (j == 0)
			{
				D[i][j] = min(D[i - 1][1], D[i - 1][2]) + arr[i][j];
			}
			else if (j == 1)
			{
				D[i][j] = min(D[i - 1][0], D[i - 1][2]) + arr[i][j];
			}
			else // j==2
			{
				D[i][j] = min(D[i - 1][1], D[i - 1][0]) + arr[i][j];
			}
		}
	}

	int ntmp = min(D[n - 1][0], D[n - 1][1]);
	ntmp = min(ntmp, D[n - 1][2]);

	cout << ntmp;

}