1149 : RGB거리

네르기·2021년 9월 5일

동적 프로그래밍 생각 타뷸레이션

알고리즘

목록 보기

46/76

어떤 문제인가?

타뷸레이션을 이용해 최솟값을 구하는 문제.

시행착오 횟수

한 번에 성공하였음.

관찰

$N$ 의 수가 작았다면(10 미만) 백트래킹으로도 풀 수 있다. 어찌되었건 모든 수를 검토해야 한다.
그리디 알고리즘을 적용할 수 없다. 기존 값의 영향을 받는다.
집에 색칠하는 경우를 그래프로 그리면 관계를 알 수 있다. 어떤 값에 대해 2개 이상의 서로 다른 값이 주어지는데, 이들 값 중 하나를 결정할 기준이 필요하다.

1차 시도 : AC

값을 저장할 2차원 배열 $D_{ij}$ 를 정의하자. 이때 $D_{ij}$ 는 첫번째 집에서 색칠을 시작해 $i$ 번째 집을 $j$ 번째 색으로 칠하기까지의 최소 비용을 나타낸다.

그래프를 그려본다면, 2번째 집 이후부터 2개의 식으로 비용이 결정됨을 알 수 있다. 예를 들어 2번째 집을 초록색으로 칠한다고 치자. 첫번째 예시를 이용하겠다.

2번째 집을 초록색으로 칠할 때 들 수 있는 비용:
-> 1번째 집, 빨강색(= 26) + 2번째 집, 초록색(= 60)
-> 1번째 집, 파란색(= 83) + 2번째 집, 초록색(= 60)

위와 같이 2가지 식으로 결정된다. 두 가지 값을 전부 쓸 수 없다. 그래서 기준을 잡아야 한다.
문제에서 요구하는 것은 최소 비용이기에, 최솟값을 쓰면 된다. 위의 경우에 대해서는 1번째 집을 빨간색으로 칠할 때의 비용과 2번째 집을 초록색으로 칠하는 비용을 더한 값이 해당된다.

이제 이를 일반화하여 수식으로 나타내자. $C_{ij}$ 는 $i$ 번째 집을 $j$ 번째 색으로 칠할 때의 비용을 나타낸다.

D_{ij} = min(C_{ij}+D_{(i-1)k}, C_{ij}+D_{(i-1)l}) \\ \text{where } l,j,k \text{ are element of } \{1,2,3\}

이제 이를 코드로 나타내면 다음과 같다.

#include <stdio.h>

int D[1001][3];

int main()
{
	int N,i,j,m;
	scanf("%d",&N);
	for(i=0;i<N;i++) {
		scanf("%d%d%d",&D[i][0],&D[i][1],&D[i][2]);
		if(i) {
			D[i][0]=D[i-1][1]+D[i][0]<D[i-1][2]+D[i][0]?D[i-1][1]+D[i][0]:D[i-1][2]+D[i][0];
			D[i][1]=D[i-1][0]+D[i][1]<D[i-1][2]+D[i][1]?D[i-1][0]+D[i][1]:D[i-1][2]+D[i][1];
			D[i][2]=D[i-1][0]+D[i][2]<D[i-1][1]+D[i][2]?D[i-1][0]+D[i][2]:D[i-1][1]+D[i][2];
		}
	}
	m=D[--i][0];
	for(j=1;j<3;j++)
		if(m>D[i][j]) m=D[i][j];
	printf("%d",m);
}