백준 2096 : 내려가기 (동적계획법 기본 이론, DP)

최적화 문제 동적 계획법 푸는 방법

 

1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다. 

 

2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 대해 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.

 

3. 재귀 호출의 입력에 이전에 선택에 관련된 정보가 있다면 꼭 필요한 정보만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 

(* 최적 부분 구조: 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 구할 수 있는 경우, 이 구조에 해당한다고 할 수 있다.)

-> 이 부분에서의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있다.

 

4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션 할 수 있도록 한다. (인덱스 활용 등)

 

5. 메모이제이션을 적용한다. 

 

 

이 방법을 적용해서 백준 2096번 내려가기 문제를 풀어보자.

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

 

 아래로 내려가면서 각각 갈 수 있는 위치가 정해져있다. 

1. 모든 경로를 만들어 보고 전체 합 중 최대치를 반환하는 완전 탐색 알고리즘을 만들어보자. 

2. 전체 답의 점수를 반환하는 게 아니라 남은 선택에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿔보자.

 

long long arr[MAX][3]; //입력받는 배열
long long DP[MAX][3];  //각 줄의 각 칸에서 가질 수 있는 값의 최대값 저장
using namespace std;
int N;
//DP[0][0], DP[0][1], DP[0][2]에 초기 첫 줄의 세 숫자가 저장되어있다. 

long long solve(int i, int j)
{
    if (i == 0) {
        return DP[i][j];
    }


    if(j == 0)
        return ret = max(arr[i][j] + solve(i-1, 0), arr[i][j] + solve(i-1,1));
    else if(j == 1)
        return ret = max(arr[i][j] + solve(i-1, 0), max(arr[i][j] + solve(i-1,1), arr[i][j] + solve(i-1, 2)));
    else
        return ret = max(arr[i][j] + solve(i-1, 1), arr[i][j] + solve(i-1, 2));
}

3. 꼭 필요한 경우만 남기고 줄인다: 최대한 중복을 많이 하도록 만들어 메모이제이션을 최대한도로 활용한다. 

-> 이 문제에서 큰 해당사항은 없다. 

-> 단, 각 최댓값을 구하려고 할 떄 중요한 점은 윗 줄의 값만 중요할 뿐 그 이전의 값이 중요하지 않기 때문에 DP의 메모리 크기를 행 = 2로 줄일 수 있다. 

 

=> 입력을 받으면서 바로 cache(DP 배열)를 사용해서 최대, 최솟값만 저장하도록 한다. 

DP[i][[j]:

- i는 열을 의미 : 0이면 왼쪽 1이면 가운데 2는 오른쪽.

- j는 최대 혹은 최소를 의미: 0이면 최댓값 저장, 1이면 최솟값 저장.

 

4. 메모이제이션을 활용한다. 

 

void input()
{
    long long a,b,c;
    long long tmpa,tmpb,tmpc;
    for(int i=0;i<N;i++)
    {
        cin >> a >> b >> c;
        if(i == 0)
        {
           DP[0][0] = a;
           DP[1][0] = b;
           DP[2][0] = c;
           DP[0][1] = a;
           DP[1][1] = b;
           DP[2][1] = c;
        }
        else
        {
            tmpa = DP[0][0], tmpb = DP[1][0], tmpc = DP[2][0];
            DP[0][0] = max(tmpa + a, tmpb + a);
            DP[1][0] = max(tmpa + b, max(tmpb + b, tmpc + b));
            DP[2][0] = max(tmpb + c, tmpc + c);
            tmpa = DP[0][1] , tmpb= DP[1][1], tmpc = DP[2][1];
            DP[0][1] = min(tmpa + a, tmpb + a);
            DP[1][1] = min(tmpa + b, min(tmpb + b, tmpc + b));
            DP[2][1] = min(tmpb + c, tmpc + c);
        }

    }
    for(int i=0;i<3;i++) {
        ansmin = min(ansmin, DP[i][1]);
        ansmax = max(ansmax, DP[i][0]);
    }
}