백준 계단(21600)

 

DP 문제를 풀게되었다.

 

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

21600번: 계단

 

 

왼쪽에서 오른쪽으로 가장 높은 계단을 만들 수 있는 경우를 구하는것이다.

 

해당 문제는 현재 차례의 자리가 만들 수 있는 가장 높은 높이를 저장하면서 구하면된다.

 

필자 같은 경우는 처음 높이는 1로 시작하면서 진행했고 이전 높이보다 현재 높이가 높으면 현재 자리는 이전높이 + 1를 해준다

 

그렇지 않는 경우는 현재 높이와 이전 높이중 작은 값을 설정해준다.

 

이후 최대 값을 찾으면 된다.

 

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

public class Main {


    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] chat = new int[N];

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

        int[] dp = new int[N];
        dp[0] = 1;

        for (int i=1 ; i < N ; i++ ) {
            int h = chat[i];

            if (h > dp[i-1]) {
                dp[i] = dp[i-1] + 1;
            } else {
                dp[i] = Math.min(dp[i-1], h);
            }
        }

        int answer = 0;

        for (int v : dp) answer = Math.max(answer, v);

        System.out.println(Arrays.toString(dp));
        System.out.println(answer);
    }

}

 

결과