[백준] 22869 : 징검다리 건너기 (JAVA)

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

 

[풀이과정]

단순히 도달여부를 확인하기만 하면 되는 문제.

O(N^2)이 2500만이어서 DFS로 풀었다가 시간초과가 발생했다. 단순히 N^2이 아닌 실제로 호출되는 함수가 컸던 부분이 원인이었음.

DP를 이용해서 도달 가능한 부분만을 true로 삼아 경로를 확인하는 방식으로 호출 횟수를 줄임.

 

[코드]

import java.util.*;
import java.lang.*;
import java.io.*;
/*
사용하는 힘은 항상 양수.
오른쪽으로 갈 때 사용해야 하는 힘이 K가 넘지 않을 때 이동 가능
끝까지 도착이 되는지의 유무 계산
*/
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, K;
    static int[] A;
    static boolean[] DP;

    public static void main(String[] args) throws IOException{
        init();
        /*
        [출력]
        이동 가능하면 YES, 불가능하면 NO 출력
        */
        for(int start = 1; start < N; start++){
            if(DP[start]){
                method(start);
            }
        }
        System.out.println(DP[N] ? "YES" : "NO");
    }

    public static void init() throws IOException{
        /*
        [입력]
        1. 돌의 개수 N, 최대 힘 K (2<=N<=5,000, 1<=K<=1,000)
        2. N개의 돌의 수 A (1<=A<=1,000)
        */
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        A = new int[N+1];
        for(int n = 1; n <= N; n++){
            A[n] = Integer.parseInt(st.nextToken());
        }

        DP = new boolean[N+1];
        DP[1] = true;
    }

    static void method(int start){
        for(int dest = start+1; dest <= N; dest++){
            if(!DP[dest]){
                //이동 가능하면 true 표시
                if(isPossible(start, dest)){
                    DP[dest] = true;
                }
            }
        }
    }

    static boolean isPossible(int start, int dest){
        int power = (dest - start)*(1 + Math.abs(A[start] - A[dest]));
        return power > K ? false : true;
    }
}