Bonjour, tout le monde!

[DP] [BOJ 1149] RGB거리 본문

Algorithm Theory/Dynamic Programming

[DP] [BOJ 1149] RGB거리

hygoni 2020. 3. 20. 23:14

 

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

www.acmicpc.net

문제

수직선 위의 N개의 집이 있을 때, 인접한 두 집의 색(R, G, B 중 하나)을 같지 않게 칠하는 최소 비용을 구하는 문제.

 

무식하게 접근하기 + 중복되는 부분 문제

모든 경우를 탐색할 때 그려지는 트리

여느 때처럼 모든 경우를 탐색해 보았을 때, 모든 전체 경우의 수는 2 * 3^N이다. N <= 1,000이니까, 말도 안되게 큰 숫자가 나와버린다. 자 그런데 그림을 보며 생각해보자. 그림에는 레벨이 4인 노드들을 R, G, B 색상에 따라서 색깔로 칠해보았다.

 

4번째에 각각의 색을 칠하는 경우는 모두 12가지가 존재한다, 그런데 이 모든 경우가 정답을 구하는 데에 있어서 필요할까? 아니다. 왜냐하면 i번째 노드의 색상을 정하는 데에는 i-1번째 집의 어떤 색상인지, 그 색상일 때의 최소 비용만 알아도 정답을 구할 수 있기 때문이다. (그 전까지 어떤 색깔을 칠했는지는 중요하지 않다.)

 

최적화를 한 후 정답을 찾아가는 과정을 그림으로 그렸다. 깊이가 늘어나도 트리의 레벨에 따른 노드의 수는 모두 같다.

 

예를 들어서 레벨이 3인 노드 중 색상이 R로 끝나는 노드는 모두 3개이다. 하지만 이를 레벨이 4인 노드에서 정답을 구할 때는 3가지 경우 중 최솟값만 알면 되므로 나머지 노드는 중요하지 않다. 즉, N번째 까지의 비용의 최솟값을 구하기 위해서는 N-1번째 집이 각각 R, G, B일 때의 최소 비용을 알고 있으면 된다. (큰 문제를 더 작은 부분 문제로 분리할 수 있다.) 이전에는 깊이가 깊어짐에 따라서 노드의 수가 2배씩 증가했지만, 최적화한 후에는 그럴 필요가 없으므로 시간복잡도는 O(N)이 된다.

 

구현

 

'Algorithm Theory > Dynamic Programming' 카테고리의 다른 글

[DP] [BOJ 2163] 초콜릿 자르기  (0) 2020.03.24
[DP] [BOJ 1003] 피보나치 함수  (0) 2020.03.22
[DP] [BOJ 1149] RGB거리  (0) 2020.03.20
[DP] [BOJ 11726] 2 x n 타일링  (0) 2020.03.19
[DP] [BOJ 9095] 1, 2, 3 더하기  (0) 2020.03.18
[DP] [BOJ 1463] 1로 만들기  (0) 2020.03.18
0 Comments
댓글쓰기 폼