동적계획법_1149_RGB거리

오늘은 백준 단계별로 문제 풀기의 동적 계획법 1 카테고리에 있는 기본 DP문제를 풀어보았다. 

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

1149번: RGB거리

 

DP문제는 크게 Top-down방식과 bottom-up방식으로 구현을 하는데, 전자는 재귀로, 후자는 반복문으로 구현을 한다. 기본적으로 재귀는 깊이가 깊어질수록 스택 오버플로우가 발생할 위험이 있기 때문에 반복을 사용하여 바틈 업 방식으로 구현을 하는 것이 효율적이라고 한다. 

재귀로 풀이를 하던, 반복문을 사용하던 동적계획법에서 가장 중요한 개념은 다음과 같이 2가지가 있다. 

• 메모이제이션
  • 메모이제이션을 하지 않는다면 동적 계획법이라고 할 수도 없고, 하는 의미도 없다. 메모이제이션이란 반복되는 값을 필요할 때마다 연산을 하는 것이 아니라, 처음 한 번 구했을 때 DP table에 저장을 하고 이후에 이 값을 필요로 하는 상황이 오면 dp table에서 값을 가져오는 방식이다. dp table은 대부분 배열을 사용하여 구현한다.
• 점화식 도출
  • 점화식을 찾는 이유는 부분의 문제를 통해서 전체적인 문제를 해결하기 위한 일반화식을 찾는 과정이다. 사실 이과정이 제일 어렵다. 필자도 잘 안되지만, 예제들을 나열해보면서 규칙성을 찾아보면서 점화식을 직접 작성하는 연습을 해야 한다.

 

그럼 이제 문제에 대한 이야기를 해보자. 문제를 풀이하기 위한 조건을 간단하게 정리해보면 다음과 같을 것이다. 

1. 같은 색으로 칠한다고 하더라도, 집마다 소요되는 비용이 다르다. 
2. 현재 집에서 인접한 두 집과는 같은 색으로 칠할 수 없다.
   1. 3번 집을 색칠해야 하는데 2,4번 집이 초록색이라면 3번 집은 초록색을 제외하고 색칠할 수 있다. 

 

필자는 처음에 문제를 읽어보고 굳이 메모이제이션이 필요한가? 생각하고 방문 배열을 색칠하고 초기화하는 것을 반복하면서 이전 집에 색칠한 색만 제외하고 최솟값을 구해서 누적합을 구했다. 한 번에 답이 도출될 것이라고 생각했다. 당연히 틀렸다. 예제 한 두 개가 맞아서 기분이 좋았었지만,, 모든 경우의 수에 대해 값을 만족하지 못했다. 그리디 알고리즘에서 전체의 최적합을 찾지 못하고 부분의 최적합을 구했던 것이다. 

그리하여 복잡하게 이전 집이 색칠한 색을 제외하고 최솟값을 구하는 과정을 하지 않고, 초기값만 초기화시킨 상태에서 이전 집에서 빨간색을 칠했다고 했을 때, 현재 집에서 색칠할 수 있는 경우의 수를 메모이제이션을 통해 각각 모두 구한 후 마지막에 최솟값을 구하는 과정을 거쳤다.

모든 경우의수를 구하기 위한 점화식은 다음과 같다. 

기본적으로 cost [n][3] 배열에는 문제에서 주어지는 입력값을 초기화해놓는다. 그 이후에는 다음의 점화식을 따라서 누적합을 구하면 된다.

cost [n][빨강] = n번째 집을 빨간색으로 칠하기 위해선 당연히 n-1번째 집은 빨강색이면 안된다. 따라서 n-1번째 집에 파랑색과 초록색을 색칠하는 비용 중에서 최솟값을 찾아서 누적합을 구해야 한다. 

ex) 1번째 집은 초기에 입력받은 값 그대로 가질 것이다. 

2번째 집을 빨간색으로 칠하고자 할 때, 1번째 집에는 빨간색을 제외한 초록 또는 파란색으로 칠해져 있어야 하므로, 2번째 집을 빨간색으로 칠하는 비용에다가 1번째 집을 파랑 또는 초록으로 칠하는 비용의 최솟값을 누적해서 더한다. 

cost [n][빨강] += cost [n-1][파랑]과 cost [n-1][초록] 값 중에서 최솟값

cost [n][파랑]+= cost[n-1][빨강]과 cost [n-1][초록] 값 중에서 최솟값

cost [n][초록]+= cost[n-1][파랑]과 cost [n-1][빨강] 값 중에서 최솟값

 

[소스코드]

package DynamicProgamming;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _1149_RGB거리 {
    static final int RED = 0;
    static final int GREEN = 1;
    static final int BLUE = 2;
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        //bottom-up으로 풀어보자 
        
        int n = Integer.parseInt(br.readLine());
        
        int cost[][] = new int[n][3];
        
        
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3 ; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        //메모이제이션 -> 재귀에 비해 눈에 띄게 보이진 않지만, 배열을 호출할때, 이전 인덱스에 저장된 누적합을 가져와 활용하기 때문에 이 또한 메모이제이션이라는 것을 알아두어라
        
        //초깃값은 그대로 두고 실행한다. 
        for(int i=1; i<n; i++) {
            cost[i][RED]   += Math.min(cost[i-1][GREEN], cost[i-1][BLUE]);
            cost[i][GREEN] += Math.min(cost[i-1][RED], cost[i-1][BLUE]);
            cost[i][BLUE]  += Math.min(cost[i-1][GREEN], cost[i-1][RED]);
        }
        
        System.out.println(Math.min(Math.min(cost[n-1][RED], cost[n-1][GREEN]),cost[n-1][BLUE]));
    }
 
}

 

 

참고 : https://st-lab.tistory.com/128