골드에그

1. 문제요약

2096번: 내려가기 (acmicpc.net)

N 줄에 0~9 숫자가 세 개씩 적혀있다. 첫 줄에서 시작해서 마지막 줄까지 내려오는 놀이이다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 주인공이 다음 줄로 내려갈 수 있는 위치라고 할 때,

얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하라.

2. 문제예제

3. 팩트추출

Fact 1 : 3 X N 표를 그래프에서 첫째 줄부터 마지막 줄까지 선택하는 경우의 수를 그래프로 나타냈을 때 DFS, BFS 로 문제를 풀 수 있겠지만, DFS 및 BFS 로 문제를 풀려면 항상 이전의 값이 고정된 값이어야 한다. 여기서는 최대값, 최소값 문제이므로 줄을 타고 내려올수록 값이 갱신되기 때문에 DFS, BFS 로 문제를 풀 수 없다.

Fact 2 : 부분문제이면서 이전의 결과 값들을 재사용하기 때문에 DP 문제로 풀 수 있다.

Fact 3 : 문제를 DP 점화식으로 풀어보면 아래와 같다.

S[i][j] = i행 j열까지 내려오면서 얻을 수 있는 최대의 점수라 할 때,
S[i][0] = max(S[i-1][0], S[i-1][1]) + map[i][0]
S[i][1] = max(S[i-1][0], S[i-1][1], S[i-1][2]) + map[i][1]
S[i][2] = max(S[i-1][1], S[i-1][2]) + map[i][2]

이 점화식에는 특징이 있다. 현재 값이 이전 행 값만 사용한다. 따라서 DP 테이블을 모두 가지고 있을 필요가 없다.

4. 문제풀이(수동)

예제 입력 1 을 minDP 수동으로 풀어본다. maxDP 는 반대 연산이므로 생략한다.

minDP[i] : i 번째 열까지 계산된 최소 비용, maxDP[i] : i 번째 열까지 계산된 최대 비용이라고 하자.

-> 0번째 행

minDP[0][0] = 1

minDP[0][1] = 2

minDP[0][2] = 3

-> 1번째 행

minDP[1][0] = min(minDP[0][0], minDP[0][1]) + map[1][0] = 1 + 4 = 5

minDP[1][1] = min(minDP[0][0], minDP[0][1], minDP[0][2]) + map[1][1] = 1 + 5 = 6

minDP[1][2] = min(minDP[0][1], minDP[0][2]) + map[1][2] = 2 + 6 = 8

-> 2번째 행

minDP[2][0] = min(minDP[1][0], minDP[1][1]) + map[2][0] = 5 + 4 = 9

minDP[2][1] = min(minDP[1][0], minDP[1][1], minDP[1][2]) + map[2][1] = 5 + 9 = 14

minDP[2][2] = min(minDP[1][1], minDP[1][2]) + map[2][2] = 6 + 0 = 6

따라서 제일 작은 6 이 정답이다.

5. 문제전략

문제 전략은 특별히 없다. 점화식을 단순히 구현하면 된다.

다른 DP 문제와 다른 점은 이전 행 정보만 필요하므로 dp[3] 테이블만 가지고 있으면 된다.

한 단계식 행을 계산할 때마다 테이블을 업데이트하면 된다.

6. 소스코드

import java.io.*;
import java.util.*;
class Main {
    static int[] maxDP;
    static int[] minDP;
    static StringTokenizer st;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        maxDP = new int[3];
        minDP = new int[3];

        int row = Integer.parseInt(br.readLine());

        for (int i=0; i<row; i++) {
            st = new StringTokenizer(br.readLine());

            int left = Integer.parseInt(st.nextToken());
            int center = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            solve(i, left,center,right);
        }
        bw.write(Math.max(maxDP[0], Math.max(maxDP[1], maxDP[2])) + " ");
        bw.write(Math.min(minDP[0], Math.min(minDP[1], minDP[2])) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    private static void solve(int index, int left, int center, int right){
        if (index == 0) {
            maxDP[0] = minDP[0] = left;
            maxDP[1] = minDP[1] = center;
            maxDP[2] = minDP[2] = right;
        } else {
            int tempMaxDP0 = maxDP[0], tempMaxDP2 = maxDP[2];
            maxDP[0] = Math.max(maxDP[0], maxDP[1]) + left;
            maxDP[2] = Math.max(maxDP[1], maxDP[2]) + right;
            maxDP[1] = Math.max(Math.max(tempMaxDP0, maxDP[1]), tempMaxDP2) + center;

            int tempMinDP0 = minDP[0], tempMinDP2 = minDP[2];
            minDP[0] = Math.min(minDP[0], minDP[1]) + left;
            minDP[2] = Math.min(minDP[1], minDP[2]) + right;
            minDP[1] = Math.min(Math.min(tempMinDP0, minDP[1]), tempMinDP2) + center;
        }
    }
}