[C] 백준 1149번 : RGB거리

 

오늘도 새로운 문제를 풀어보았습니다 !

분명 실버 1 정도의 난이도를 고른 건데,,,,

왜 여태 풀었던 DP 문제들 중 제일 어려웠던 걸까요? ( -᷅_-᷄) 

(결국은 ,, 인터넷의 힘을 빌렸답니다.. ㅎㅎ)

.

백준 1149번

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

1149번: RGB거리

 

저는 이 문제를 처음 봤을 땐 'dp 배열로 풀면 되겠다!' 라고 생각했습니다.

1번 집부터 N번까지 index를 증가시키면서 dp 배열을 update 해주면 최적화된 값이 나올 것이라 생각했기 때문입니다.

그래서 dp 1차원 배열을 만든 후, dp[집의 개수] = 최소 비용이라고 설정하였습니다.

그 이후 이전 집과 index만 겹치지 않게 dp 배열을 update 해주었습니다.

.

이렇게 코드를 작성하니 아래의 예시에서는 코드가 잘 작동하였습니다.

1149번 예제

 

하지만 제가 임의로 작성해본 예시에 대해서는 틀린 답이 나왔습니다. ㅠ

 

예제 2

 

제가 처음에 작성한 코드는 dp 배열을 1차원으로 만들었기 때문에 현재까지 탐색한 집 정보만 포함합니다.

따라서 집을 계속 탐색하다가 잘못된 값임을 (최솟값이 아님을) 알게 되더라도 이전으로 되돌릴 수 없습니다.

.

예시 1을 보면 1번 집에서 제일 작은 값인 26이 빨간색으로 칠할 때 드는 비용입니다. (첫 번째 index)

따라서 min 비교를 통해 dp[1]에 26을 저장하였습니다. (저는 배열을 1번 index부터 사용하였습니다.)

이렇게 되면 1번 집을 빨간색으로 칠한다고 확정 지어버리는 것입니다.

이 문제는 운이 좋아서 정답이 나왔지만, 예제 2를 보면 이 방식이 틀렸음을 확실히 알 수 있습니다.

.

제가 생각한 방식으로 예제 2를 보면, 1번 집에서는 최솟값인 10 (dp[1] = 10)을 선택합니다.

이후 1번 집을 색칠한 index(index 1)를 제외하고 생각했을 때 최솟값인 것은 1000(index 2)과 또 1000(index 3)입니다.

2번 집에는 9라는 적은 비용을 가진 색깔이 있지만,

dp[1]을 이미 10이라고 선택해버렸기 때문에 되돌아갈 수 없습니다.ㅠ

.

저는 이것을 어떻게 해결하면 좋을까.. 고민하다가 무작정 while 문을 사용해보았습니다.ㅎㅎㅎ

(N 범위 자체가 1000까지이고, 주어진 색깔이 3가지밖에 없어서 어쩌면 풀리지 않을까 싶었습니다...)

저는 모든 case를 다 계산해보고 min을 구해보았습니다.

여기서 반복 횟수를 줄이기 위해, 현재까지 구한 합이 현재 min보다 작으면 다음 반복을 하는 식으로 설정하였습니다.

제가 위에서 언급한 예시 2개와 몇 개의 간단한 예시를 돌려보았을 때는 답이 잘 나왔지만,

역시는 역시.. 시간 초과가 뜨더라구요ㅠㅠ..

(궁금하지 않겠지만..코드가 궁금하다면 더보기를 확인해주세요..ㅎ)

import java.util.Scanner;

class Main {

	static int N;
	static int[][] input=new int[1001][4];
	static int[] visited=new int[1001];
	static int[] sum=new int[1001];
	static int min=1000*1000+1;
	static int depth=1;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner keyboard=new Scanner(System.in);
		
		N=keyboard.nextInt();
		for (int i=1; i<=N; i++)
			for (int j=1; j<=3; j++)
				input[i][j]=keyboard.nextInt();
		keyboard.close();
		
		outerloop:
		while(true) {
			
			visited[depth]++;
			if (visited[depth-1]==visited[depth])
				visited[depth]++;
			
			while(visited[depth]>3) {
				visited[depth]=0;
				depth--;
				if (depth<=0)
					break outerloop;
				visited[depth]++;
				if (visited[depth-1]==visited[depth])
					visited[depth]++;
			}
		
			sum[depth]=sum[depth-1]+input[depth][visited[depth]];
			if (sum[depth]>=min)
				continue;
			
			depth++;
			if (depth>N) {
				if (sum[depth-1]<min)
					min=sum[depth-1];
				depth--;
			}

		}
		System.out.println(min);
	}

}

 

지금 작성한 코드를 좀 더 수정해볼까 싶었지만

문제 시간제한이 너무 짧기도 하고, 더 최적화할 부분을 찾기가 힘들었습니다.

그래서 인터넷에 다른 분들이 푼 알고리즘을 조금 참고해보았습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 1000*1000

int input[1001][4];
int dp[1001][4];

int min(int x, int y) {
	return x < y ? x : y;
}

int main() {
	int N;
	scanf("%d", &N);
	
	// 입력
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= 3; j++)
			scanf("%d", &input[i][j]);
	
	// dp 배열 채우기
	dp[1][1] = input[1][1];
	dp[1][2] = input[1][2];
	dp[1][3] = input[1][3];

	for (int i = 2; i <= N; i++) {
		dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + input[i][1];
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][3]) + input[i][2];
		dp[i][3] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][3];
	}

	// 출력
	int min = MAX + 1;
	for (int i = 1; i <= 3; i++)
		if (dp[N][i] < min)
			min = dp[N][i];
	printf("%d", min);
	return 0;
}

 

저는 그동안 dp 배열을 1차원으로 잡았었는데, 2차원으로 잡는 방법이 있더라구요...! 나 진짜 바본가ㅠ;

이렇게 되면 현재 구하는 index (여기서는 i)에서 R을 할 때, G를 택할 때, B를 택할 때를 모두 구할 수 있습니다.

그리고 i번째 집의 색깔을 정할 때, i-1번째 집을 확인합니다.

i번째 집 -> 빨간색(index 1)으로 칠하려면

i-1번째 집 -> 초록 색(index 2) 아니면 파란색(index 3)이어야 합니다.

따라서 i-1번째 집을 초록색, 파란색으로 칠했을 때의 비용 중 최솟값에 빨간색을 칠하는 비용을 더하면 됩니다.

=> dp[i][1] = min(dp[i-1][2], dp[i-1][3]) + input[i][1]

즉, 각 집마다 빨간색, 초록 색, 파란색을 칠하는 경우를 모두 고려한 후 조건에 맞게 활용하는 것입니다.

.

위의 예시 2번의 dp 배열을 구해보면 다음과 같습니다.

dp 배열

 

{ }에 적힌 부분은 1번 집부터 선택한 색깔의 index 입니다.

(ex. dp[2][1] -> 1번 집 2번 index (초록 색), 2번 집 1번 index (빨간색) 선택)

이렇게 dp 배열을 채운 후 dp[N][1] ~ dp[N][3] 중 최솟값을 찾으면 됩니다!

.

DP는 정말 왜 이렇게 어려운 걸까요?...^^

앞으로 한참은 더 풀어봐야 할 것 같습니다...