[백준] 22871 : 징검다리 건너기 (large) (DP) - JAVA

알고리즘스터디 (dp)

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

 

 

# 문제

 N$N$개의 돌이 일렬로 나열 되어 있다. N$N$개의 돌에는 왼쪽부터 차례대로 수 A1A2...Ai...AN$A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

1. 항상 오른쪽으로만 이동할 수 있다.
2.  i$i$번째 돌에서 j(i<j)$j(i < j)$번째 돌로 이동할 때 (j−i)$(j - i)$ × (1 + |Ai−Aj$A_{i} - A_{j}$|) 만큼 힘을 쓴다.
3. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K$K$이다.

가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 K$K$의 최솟값을 구해보자.

 

# 예제

입력 : 첫 번째 줄에 돌의 개수 N$N$이 공백으로 구분되어 주어진다. 두 번째 줄에는 N$N$개의 돌의 수 Ai$A_i$가 공백으로 구분되어 주어진다.

5
1 4 1 3 1

 

출력 :  가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 가능한 K$K$의 최솟값을 출력한다.

2

 

 

# 필요개념

바로 최종목적지까지의 경로를 구하기 힘드므로 dp를 이용하였다. 입력을 받는 input[] 외에, 원하는 목적지까지 필요한 힘을 dp에 넣기로 했다. 

 

이 문제에서 k를 잘 이해할 필요가 있는데, 

원하는 목적지까지 가는 경우의 수는 굉장히 많다. 그중에서 k의 상한선(max)의 최솟값을 구해야하는 문제였다. 어떤 경유지를 거쳐갈 때, 경유지마다 도착하는 힘의 최대값이 k이고 모든 경우의 수에서 k를 구한 후 그의 최소값을 구해야한다.  즉, 일단은 계속 최소의 힘들 들여 경유지마다 이동을 해야한다는 것이다.

 

 

 

idx = 3 에 있을 때, dp[0] + power(3, 0) / dp[1] + power(3, 1) ... 을 하나하나 대조해야 하기 때문에 이중for문을 사용했다.

N의 최대가 5000이기 때문에 이중for문을 사용해도 시간초과가 나지는 않는다 !

 

# Code

import java.util.*;
import java.io.*;

import static java.lang.Math.*;

public class Main {
    static int[] inputs;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        inputs = new int[N];
        long[] dp = new long[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            inputs[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1 ; i < N ; i++) {
            dp[i] = Long.MAX_VALUE;
            for (int j = 0 ; j < i ; j++) {
                dp[i] = min(dp[i], max(power(i, j), dp[j]));
            }
        }

        System.out.println(dp[N - 1]);
    }

    public static long power(int big, int small) {
        return (long) (big - small) * (1 + abs(inputs[big] - inputs[small]));
    }
}

 

# 결과