골드에그

1. 문제요약

12865번: 평범한 배낭 (acmicpc.net)

주인공의 배낭은 최대 K 크기 만큼 물건을 넣을 수 있다. 배낭에 넣을 수 있는 물건들의 무게와 가치가 주어질 때, 배낭에 넣을 수 있는 물건들의 가치 최댓값을 출력하시오.

2. 문제예제

3. 팩트추출

"워낙 유명한 문제라 DP 알고리즘 문제라는 것을 알고 문제를 푸는 것이 아니라

어떻게 DP 로 접근했을까 생각하고 아이디어를 정리해보았다."

Fact 1 : 각 물건들을 고르거나 고르지 않는 모든 경우의 수를 고려해보면 쉽게 문제를 해결할 수 있다. 하지만, O(2^N) 시간복잡도가 필요하며 너무 많은 시간이 소요된다. 물건이 하나씩 추가될 때마다 기존 시간의 2배 정도 시간이 필요한 것이다. 물건에만 포커스를 맞춘 경우인데 이러한 구조는 이미 경우의 수 일부에서 배낭이 꽉 찬 경우인데도 어쩔 수 없이 탐색할 수 밖에 없다. 위 예제 1에서 첫 번째 아이템을 선택하면 무게가 6으로 그 다음은 7-6=1무게만큼 필요한데 1무게를 찾기 위해서 모든 조합을 다 찾아야 한다는 것이다. 여기서 힌트를 얻을 수 있다.

내가 지금 필요한 무게에 대한 최대값을 바로 찾을 수 있다면 그런 수고를 덜 수 있다. 위 예제에서는 1무게에 대한 최대값 말이다. 다시 말해 물건과 무게 두 곳에 포커스를 맞추어 정답을 구하는 것이다.

Fact 2 : i 번째 물건까지 보았을 때 가치가 최대인 무게들을 구한다는 것은 부분문제처럼 보인다. 여기서 구하려고 하는 최종 결과값도 최대 가치를 만들려고 하는 것이기 때문이다. 부분 문제이고 작은 문제들의 정답이 다음 문제들에게 영향을 미친다면 DP (Dynamic Programming) 문제이다. DP[i][j] 를 i 번째 물건까지 보았을 때 j 무게에서 최대 가치라고 할 때 아래와 같은 수식이 만족한다.

DP[i][j] = max(v[i] + dp[i-1][j - w[i]], dp[i-1][j])

각 가방의 가치 : v[n] / 각 가방의 무게 : w[n]

dp[i-1][j] 는 이전 물건까지만 고르고 현재 물건을 고르지 않는 경우이고, v[i] + dp[i-1][j-w[i]] 는 이전 물건도 고르고 이번 물건도 고르는 경우이다. j-w[i] 수식을 보면 배낭의 남은 무게보다 현재 물건의 무게가 작아야 한다는 것을 알 수 있다. 물건을 탐색했을 때 가방에 넣을 수 있다면 해당 무게로 이전까지 선택한 최대치에 현재 가치를 더해서 최대치를 갱신한다.

Fact 3 : 점화식도 분명 현재 물건을 넣는 경우와 넣지 않는 경우의 수가 필요한 것이 분명한데 O(2^N) 이 되지 않는 점을 이해해야 한다. 모든 조합의 경우의 수를 구해서 문제를 푸는 것이 아니라 각 단계마다 정답을 구해 이전 경우의 수를 상쇄시키는 것이 특징이다. 이전 값만 보고 판단한다. DP 특징이기도 하다. 또한 해당 시점에서 배낭의 무게를 1차이로 모두 구해 탐색하지 않고 바로 답을 구하는 것을 볼 수 있다.

4. 문제풀이(수동)

문제 예제 입력 1번의 DP 테이블을 만들었을 때 다음과 같다.

위 DP 점화식을 토대로 i 가 1부터 4까지 j 행을 차례로 구한다. 

dp[3][7] 을 살펴보면, dp[3][7] 은 dp[2][7] 과  dp[3][7-(3번 물건의 무게)] + v[3] 둘 중 큰 값을 저장하게 된다. dp[3][4] 값은 8이고 v[3] 은 6이므로 최종적으로 dp[2][7] 은 13, dp[3][7] 은 14이므로 dp[3][7] 에는 14가 저장된다.

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 도출한 DP 방정식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, K;
    private static int[] weight, value;
    private static int[] dp;
    private static void knapsack() {
        for (int i = 1; i <= N; i++) {
            for (int j = K; j - weight[i] >= 0; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        weight = new int[N+1];
        value = new int[N+1];
        dp = new int[K+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }
        knapsack();
        System.out.println(dp[K]);
    }
}

1. 문제요약

1520번: 내리막 길 (acmicpc.net)

지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.

2. 문제예제

3. 팩트추출

Fact 1 : 전형적인 BFS 와 DFS 문제인 것처럼 보이지만, 입력의 범위를 보면 완전 탐색 시 시간 초과가 발생할 수 있다. 최대 칸 수가 500 * 500 으로 250000 이며 상하좌우 4방향으로 움직일 수 있으니 4 의 250000 제곱 경우의 수가 존재한다. 경우의 수를 줄일 수 있는 방법을 찾아야 한다.
 

Fact 2 : 문제 예제를 살펴보면 전체 문제의 답이 작은 부분 문제의 답의 합으로 구성되어 있다. 50 번 지점에서 목적지까지 가는 경로의 수는 45번 지점에서 가는 경로의 수 + 35번 지점에서 가는 경로의 수로 이루어져 있다. 35번 지점이나 30번 지점, 27번 지점은 경로의 수가 하나로 나중에 이 지점을 방문하더라도 계산할 필요가 없다. 즉 DP 문제이다.

Fact 3 : 기존 DFS 나 BFS 에서 사용하던 visited 배열을 응용하여 "해당 지점에서 목적지까지 가는 경로의 수" 로 생각하여 해당 값을 재활용하면 탐색 범위를 줄일 수 있다. 여기서 중요한 점은 DFS 와 BFS 의 visited 배열 활용도가 조금 다르다는 것이다. BFS 는 주변부터 탐색하기 때문에 단순 방문했는지 여부만 파악할 수 있지만 DFS 는 한 가지 경우의 수부터 모두 탐색하고 다시 원래 위치로 돌아오기 때문에 수행 도중 visited 배열을 오염시킨다면 그 경로는 다시 탐색하지 않아도 된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.

Fact 4 : DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.

4. 문제풀이(수동)

문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.

손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int M, N;
    static int[][] map;
    static int[][] dp;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        dp = new int[M][N];

        for(int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                map[j][i] = Integer.parseInt(st.nextToken());
            }
        }
        initDP();
        System.out.println(dfs(0, 0));
    }
    private static void initDP() {
        for(int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                dp[j][i] = -1;
            }
        }
    }
    private static int dfs(int x, int y) {
        if(x == M-1 && y == N-1){ return 1; }
        if(dp[x][y] != -1) return dp[x][y];

        dp[x][y] = 0;
        for (int i=0; i<4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
            if (map[x][y] <= map[newX][newY]) continue;

            dp[x][y] += dfs(newX, newY);
        }
        return dp[x][y];
    }
}

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;
        }
    }
}

1 . DP 조건

① . Overlapping Subproblem : 분할된 작은 문제들이 겹치면서 중복된다.

② . Optimal Structure : 분할된 작은 문제의 최적해들을 결합하면 전체 문제의 최적해가 된다.

2 . DP 특징

① . DP 는 문제를 작게 나누어 최종 문제를 조건부 점화식을 통해 구현할 수 있을 때 가장 이상적이다.

② . 작은 문제의 답이 중복되지 않는 구조라면 DP 가 비효율적일 수 있다.

③ . 분할정복과 동적계획법은 작은 문제로 분할하여 문제를 해결한다는 점에서 유사하지만, 분할정복은 작은 문제의 답을 활용하지 않는 반면에 동적계획법은 분할된 문제들의 답을 활용한다는 점이다.

3 . DP 풀이 방식

DP 를 풀이하는 방법에는 top-down 과 bottom-up 방식이 있다.

① . top-down (Memoization) : 시작 위치에서 마지막 위치로 내려가며 최종 답을 점화식을 통해 먼저 구현하고 중간 중간 작은 문제들의 답을 구해 문제를 푼다. 이 때 중간 작은 문제들의 답은 DP 특성 상 중복되기 때문에 결과 값을 저장하여 바로 로드한다. 보통 재귀와 lookup table 를 사용하며 프로그램 스택을 사용하는 것이 특징이다.

② . bottom-up (Tabulation) : 마지막 위치에서 시작 위치로 올라가며 작은 문제들의 답을 풀어가면서 최종 답을 구한다. 보통 반복문으로 구성된다.

(위 3-1 과 3-2 에서 정의한 "시작 위치" 와 "마지막 위치" 는 문제 풀이를 하기 위한 탐색 경로 상의 위치이다.)

③ . 두 방식 모두 무한루프를 방지하기 위해 기저사례가 필요하다. 이 기저사례는 이전 항들로 표현되지 않는 상태의 값을 의미한다.

4 . 재귀 함수의 구간 별 의미

def recursive (index, output) {
	If ( 탈출 조건 with index ) {
		재귀함수에서 빠져 나와야 하는 기저사례
	}
	
	반복문 ( 부모가 여러 개 있을 경우 반복문 사용함. 부모가 한 개나 두 개인 경우 필요 없음 )
	{
		If ( /* 탐색하지 않아도 되는 부분들 */ ) continue
		recursive 함수 호출 (자식 탐방일 수 있고 상대 탐방일 수 있다)
	}
	부모로 돌아갈 때마다 해야될 일 (보통은 부모의 상태로 복원해야 하는 코드)
    해당 경우의 수 마지막 부분까지 온 경우이므로 마지막 자식 호출하고 난 다음에 해야될 일 (보통 계산)
}

1. 문제요약

leetcode.com/problems/dungeon-game/

악마가 공주를 납치해 N x M 던전판 가장 우측 하단에 감금했다.

가장 좌측 상단에 있는 왕자가 공주를 구하기 위한 최소 체력은 얼마인지 구하시오.

룰은 다음과 같다.

① 왕자는 우측 또는 하단 방향으로만 한 칸씩 갈 수 있다.

② 각 방에는 음의 정수 또는 양의 정수가 있다. 왕자가 이동할 때 이 숫자에 영향을 받는다.

음수라면 숫자만큼 체력이 삭감되고, 양수라면 숫자만큼 체력이 상승한다.

③ 왕자 체력이 0 이거나 음수가 되면 게임은 종료된다.

2. 문제예제

3. 팩트추출

Fact 1 : N X M 던전판을 작게 축소하여 작은 문제들의 결합으로 구성할 수 있고 이 작은 문제들의 최적해들을 결합하면 전체 문제의 최적해가 된다. 따라서 Dynamic Programming 문제이다.

Fact 2 : dp[i,j] 를 dungeon[i,j] 에서 최소값이라고 할 때, dp[i,j] 는 dp[i,j+1] 과 dp[i+1,j] 중 최소값에 dungeon[i,j] 를 더한 값이다. dungeon[i,j] 값이 양수라면 0을 음수라면 절대값을 더한다. 문제에서 최소값을 구하라고 명시하고 있으므로 양수일 때는 신경 쓸 필요가 없다. 음수를 다 더한 값이 그 경로의 최소값이 된다.

Fact 3 : 일반적인 DP 문제와는 달리 해당 점화식에서 바로 값을 구할 수 없다. 점화식으로 표현되는 dp[i,j+1] , dp[i+1,j] 이 두 항이 다른 값들이 먼저 계산되어야 계산할 수 있기 때문이다. 그래서 기저 사례부터 먼저 구하고, 기저 사례만 필요한 마지막 행과 열을 구해 나머지 부분들을 계산하여야 한다.

Fact 4 : Top-Down 방식이던 Bottom-Up 방식이던 무한 루프를 방지하기 위해 기저 사례가 필요하다. 점화식으로 표현된 dp[i,j+1] 과 dp[i,j+1] 이 두 항이 이전 항들로 표현되지 않을 수 있을 때 기저 사례라고 한다. 이 문제에서는 공주가 있는 위치가 기저 사례이다.

4. 문제풀이(수동)

예제 1번을 기준으로 문제풀이를 진행한다.

기저 사례를 먼저 구하면, 공주 위치에 있는 값이 -5 이므로 6 이라는 최소 체력이 필요하다.  

(만약 값이 양수였다면 1 이라는 최소 체력이 필요할 것이다.)

Fact 3 에서 정리한 바와 같이 공주 위치를 기준으로 좌측 행 상단 열을 구하면 다음과 같다.

마지막 행과 마지막 열은 각각 이전 행과 이전 열 한 개씩만 필요하기 때문에 풀 수 있다.

이 값들을 기준으로 나머지 부분들도 계산하면,

최소 체력은 7 이라는 것을 알 수 있다.

5. 문제전략

위 수동풀이처럼 공주님 위치에서 마지막 행 열을 구한 후, 나머지 부분들을 계산할 수 밖에 없다.

Top-Down 방식, Bottom-Up 방식으로 모두 풀 수 있다.

6. 소스코드

Top-Down

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int row_size = dungeon.size();
        int column_size = dungeon[0].size();
        vector<vector<int>> dp(row_size, vector<int>(column_size));
        return calculate(dungeon, 0, 0, dp);
    }

    int calculate(vector<vector<int>>& dungeon, int i, int j, vector<vector<int>>& dp) {
        // 기저 사례
        if (i == dungeon.size() - 1 && j == dungeon[0].size() - 1)
            return dungeon[i][j] > 0 ? 1 : -dungeon[i][j] + 1;
        // 메모이제이션
        if (dp[i][j] != NULL)
            return dp[i][j];
        // 마지막 행
        if (i == dungeon.size() - 1)
            return dp[i][j] = max(1, calculate(dungeon, i, j + 1, dp) - dungeon[i][j]);
        // 우측 마지막 열
        if (j == dungeon[0].size() - 1)
            return dp[i][j] = max(1, calculate(dungeon, i + 1, j, dp) - dungeon[i][j]);

        return dp[i][j] = max(1, min(calculate(dungeon, i + 1, j, dp) - dungeon[i][j],
                calculate(dungeon, i, j + 1, dp) - dungeon[i][j]));
    }
}

Bottom-Up

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int r=dungeon.size();
        int c=dungeon[0].size();
        vector<vector<int>> dp(r,vector<int>(c));

        for(int i=r-1;i>=0;--i)
        {
            for(int j=c-1;j>=0;--j)
            {
                if(i==r-1 && j==c-1)     // 초기 값으로 맨 오른쪽 밑 (Princess Cell)
                    dp[i][j] = max(1,-dungeon[i][j]+1);
                else if(i==r-1)     // 마지막 행
                    dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]);
                else if(j==c-1)     // 우측 마지막 열
                    dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j]);
                else
                    dp[i][j] = max(1,min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

1. 문제요약

www.acmicpc.net/problem/13263

높이가 a 인 나무 n 개를 전기톱을 이용해서 모든 나무를 완전히 자르려고 한다.

모든 나무를 완전히 자르는데 필요한 충전 비용의 최솟값을 구하는 프로그램을 작성하라.

룰은 다음과 같다.

① 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 쓰고 난 뒤에는 바로 충전해야 한다.

② 완전히 잘려진 나무가 없다면 전기톱은 충전할 수 없으며 높이가 0 이 되어버린 나무들 번호 중 최대값의 충전비용을 사용한다.

③ A 배열은 각 나무들의 높이이고 B 배열은 전기톱의 충전비용이다.

④ a1 = 1 이고 Bn = 0 이고 a1<a2<…<an, b1>b2>…>bn 을 만족한다.

2. 문제예제

3. 팩트추출

Fact 1 : 문제지문에서 Bn 은 0 이라고 명시하고 있다. Bn 나무의 높이를 0 으로 만들 수 있는 최소 비용을 구할 수 있다면 나머지 나무들은 0 의 비용으로 모두 자를 수 있다. 즉, 문제가 "모든 나무를 완전히 자르는데 필요한 최소 비용" 에서 "Bn 나무의 높이를 0 으로 만들 수 있는 최소 비용" 으로 바뀐다.

Fact 2 : 전기톱을 사용해서 나무의 높이를 한 칸씩 줄일 때마다 충전해야 된다. 이 때 나무의 높이가 0 인 것이 하나라도 있어야 최소한 그 나무의 충전 비용으로 모든 나무를 완전히 자를 수 있다. 문제지문에서 A1 = 1 이고 A 배열은 단조증가배열인 점을 감안할 때, 첫 번째 나무를 먼저 베어야 게임 시작이 가능하다.

Fact 3 : 최소 비용을 구하는 것이기에 한 나무를 베기로 정했으면 중간에 다른 나무를 벨 필요는 없다.

Fact 4 : 위 사실들을 기반으로 문제를 정리하면 다음과 같다.

1번부터 N번까지의 나무가 있었을 때 1번부터 베기 시작해서 N번까지 베는 최소비용을 찾는다.

문제풀이 부분경로는 순차적이며 중간 경로를 건너 뛸 수 있다는 특징을 가지고 있다. 예를 들어 1번 2번 3번 … N번까지 차례대로 베거나, 1번에서 N번으로 바로 벨 수 있다.

4. 문제풀이(수동)

dp[i] : i 번째 나무를 높이 1로 만드는데 필요한 최소비용

a[i] : i 번째 나무 높이 , b[j] : j 번째 나무 충전비용이라고 할 때,

점화식은 dp[i] = min(1<j<i) dp[j] + a[i]b[j] 와 같다. 이 때 i 는 1부터 N까지이다.

다음은 예제 입력 2번을 기준으로 수동풀이이다.

dp[0] = 0

dp[1] = dp[0] + a[1]b[0] = 0 + 2*6 = 12

dp[2] = dp[0] + a[2]b[0] = 0 + 3*6 = 18

        = dp[1] + a[2]b[1] = 12 + 3*5 = 27

dp[3] = dp[0] + a[3]b[0] = 0 + 10*6 = 60

        = dp[1] + a[3]b[1] = 12 + 10*5 = 62

        = dp[2] + a[3]b[2] = 18 + 10*4 = 58

dp[4] = dp[0] + a[4]b[0] = 0 + 20*6 = 120

        = dp[1] + a[4]b[1] = 12 + 20*5 = 112

        = dp[2] + a[4]b[2] = 18 + 20*4 = 98

        = dp[3] + a[4]b[3] = 58 + 20*3 = 118

dp[5] = dp[0] + a[5]b[0] = 0 + 30*6 = 180     ---> ①

        = dp[1] + a[5]b[1] = 12 + 30*5 = 162     ---> ②

        = dp[2] + a[5]b[2] = 18 + 30*4 = 138     ---> ③

        = dp[3] + a[5]b[3] = 58 + 30*3 = 148     ---> ④

        = dp[4] + a[5]b[4] = 98 + 30*2 = 158     ---> ⑤

따라서 정답은 138 이다. 계산은 15번 소요되었다.

5. 문제전략

위 수동풀이처럼 순수 DP(점화식)로 푼다면, O({N*(N-1)}/2) 복잡도가 발생한다.

문제에서 N 이 100,000 이기 때문에 시간 제한(2초) 이내에 풀 수 없다. 다른 전략이 필요하다.

Solving Strategy Item 1 :

dp[i] = min(1<j<i) dp[j] + a[i]b[j] 점화식에서 변화하지 않는 부분 a[i] 를 이용한다.

a[i] 부분을 x 로 치환하면 y = bx+c 꼴 일차방정식으로 표현할 수 있는데

a 는 단조증가 b 는 단조감소 이기 때문에 마치 볼록한 껍질 형태의 그래프들로 표현할 수 있다.

convex hull 이라고 부른다. 예제 입력 2번을 실제 그래프로 표시해보자.

4번 문제풀이(수동) 을 자세히 보면 ① ② ③ ④ ⑤ 번 함수들이 계속 반복되는데 이 함수들을 그래프로 표시하면 위 그래프와 같다. 여기서 특징점들이 보인다.

파랑색 함수는 비교대상이 아니라는 점이다. 녹색 함수와 빨간 함수들만 보면 어느 X 값이라도 최소값을 확인할 수 있다.

일차함수이고 기울기가 낮아지는 함수들이다보니, 두 함수의 교점 X 좌표들을 비교만 해보아도 제외 대상을 가려낼 수 있다. 다시 말해 A 함수와 B 함수의 교점보다 B 함수와 C 함수의 교점이 낮다면 B 함수는 볼 필요 없는 것이다.

필요 없는 함수들을 제외하면서 그래프들의 교점들을 모아 두었다가 그 교점들과 A[i] 즉 x 값을 비교한다. x 값이 커질 때의 함수를 찾으면 x 값을 대입하여 y 값을 구할 수 있다.

Solving Strategy Item 2 :

그래프의 교점들과 비교할 때 이분탐색을 이용하면 O(NlogN) 시간복잡도까지 줄일 수 있다.

Solving Strategy Item 1번을 통해 교점들 x 좌표가 오름차순으로 정렬이 되기 때문에 순차적으로 값을 찾기 보다는 이분탐색으로 찾는 것이 훨씬 빠르다.

6. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 100000;

// 일차 함수 표현 : f(x) = ax+b
struct Line {
	long long a, b;
	double cross_x;

	Line(long long a_, long long b_, double cross_x_ = 0) :a(a_), b(b_), cross_x(cross_x_) {}
};

// 두 함수의 교차점 
double cross(const Line& f, const Line& g)
{
	// f 를 f.ax+f.b 라 하고, g 를 g.ax + g.b 라 할 때 x 를 왼쪽에 남겨두고 이항하면,
	return (g.b - f.b) / (f.a - g.a);
}

// 이분 탐색
int binary_search(vector<Line>& line, long long key)
{
	int position = 0;
	int left = 0, right = line.size() - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (line[mid].cross_x < key) {
			position = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	return position;
}

long long dp[MAX];

int main()
{
	// 입력 예제 2번
	int n = 6; // N 나무
	vector<int> a = { 1,2,3,10,20,30 }; // 나무 높이
	vector<int> b = { 6,5,4,3,2,0 }; // 충전 비용

	vector<Line> line_stack;

	// dp[0] 은 항상 0 이므로, 1부터 시작
	for (int i = 1; i < n; ++i)
	{
		// 나무가 N 개이면, N-1 개의 점화식이 존재함
		Line g(b[i - 1], dp[i - 1]);    // y = ax+b 에서 차례대로 (a, b)

		while (line_stack.size() >= 1)
		{
			g.cross_x = cross(g, line_stack.back());

			if (g.cross_x < line_stack.back().cross_x) // 교점을 통해 비교. 위에 있는 함수는 버림.
				line_stack.pop_back();
			else
				break;
		}
		line_stack.push_back(g);

		int x_position = 0;
		x_position = binary_search(line_stack, a[i]);
		// y 값 계산
		dp[i] = line_stack[x_position].a * a[i] + line_stack[x_position].b;

	}
	cout << dp[n - 1] << endl;
	return 0;
}