[Java] 백준 22871번 - 징검다리 건너기(large)

• 문제
  • 링크 : https://www.acmicpc.net/problem/22871
  • 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 K의 최솟값 구하기

 

• 조건
  • 왼쪽 → 오른쪽으로만 이동 
  • i번째 돌 → j번째 돌 (i < j) 이동할 때 사용되는 힘 = (j - i) X (1 + |Ai - Aj|)
  • K : 나열된 돌을 전부 건널 때 사용하는 힘의 최댓값

 

• 입력
  • 첫번째 줄
    • N : 돌의 개수
    • 2 ≤ N ≤ 5,000
  • 두번째 줄
    • Ai : N개의 돌의 수가 공백으로 구분되어 있음
    • 1 ≤ Ai ≤ 1,000,000

 

• 출력
  • K의 값

 

• 로직 1)
  • 이동할 때 필요한 모든 경우의 힘의 크기 구하기
  • 모든 경우의 K 값을 구하고 그 중 가장 작은 값 출력하기

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

// 징검다리 건너기(large)
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 돌의 개수
        int answer = -1; // K의 최솟값
        int[][] power = new int[5001][5001]; // 돌끼리 이동하는 힘

        // 돌에게 주어진 수 입력받기
        for(int i=1; i<=n; i++) {
            power[i][0] = sc.nextInt();
        }

        // 돌끼리 이동하는 힘 구하기
        for(int i=1; i<n; i++) {
            for(int j=i+1; j<=n; j++) {
                power[i][j] = (j-i) * (1 + Math.abs(power[i][0] - power[j][0]));
            }
        }

        // 모든 경우의 수를 계산해서 K의 최솟값 구하기
        Stack<int[]> stack = new Stack<>();
        List<int[]> list = new ArrayList<>(); // 이동한 순서

        for(int i=2; i<=n ;i++) {
            int[] tmp = new int[]{1, i};
            int k = power[1][i]; // 각 경우의 k 값
            stack.add(tmp);
            list.add(tmp);

            while(true) {
                if(tmp[1] != n) { // 돌을 건널 때까지 건너는 경우 추가
                    tmp = new int[]{tmp[1], tmp[1]+1};
                    stack.add(tmp);
                    list.add(tmp);
                } else { // 돌을 전부 건너는 경우
                    k = findK(list, power); // k값 구하기
                    if(answer == -1 || k < answer) answer = k;

                    tmp = stack.pop();
                    list.remove(list.size()-1);
                    if(!stack.isEmpty()) {
                        tmp = stack.pop();
                        list.remove(list.size()-1);

                        tmp = new int[] {tmp[0], tmp[1]+1};
                        stack.add(tmp);
                        list.add(tmp);
                    } else break;
                }
            }
        }

        System.out.println(answer); // K의 최솟값 출력
    }

    // 가장 작은 K의 값 찾기
    public static int findK(List<int[]> list, int[][] power) {
        return list.stream()
                .mapToInt(value -> power[value[0]][value[1]])
                .max()
                .getAsInt();
    }
}

 

• 결과
  • 실패 - 시간초과