골드에그

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. 문제요약

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