[BOJ] 백준 2579 - 계단 오르기 (자바)

DP ..,,,..

이것도 초등부 문제...?

초등부라....... 하하하하

조건

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

풀이

1. 한칸이나 두칸 이동할 수 있다.

2. 연속된 세개의 계단을 밟으면 안된다는 뜻는 (1칸 이동 -> 1칸 이동) 이 불가하다는 뜻이다.

그렇다면 해결 방법은 (2칸이동 + 1칸이동), (1칸이동 + 2칸이동), (2칸이동 + 2칸이동) 경우의 수가 생긴다.

이때 2칸이동을 했을경우에는 이전에 2칸이동을 했을 경우와 1칸 이동을 했을 경우가 생긴다.

2칸이동을 했을때와 1칸이동을 했을때의 최대값을 비교하여 2칸이동한 위치를 더해줘야한다.

여기서 dp 2차원 배열을 만들어 dp[x][0] 때는 1칸이동, dp[x][1] 일때는 2칸이동을 나타냈다.

3. 마지막 계단을 밟아야 하므로 그 위치에 저장된 값을 출력해준다.

코드를 보자.

소스

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main {
 
    static BufferedReader br;
 
    public static void main(String[] args) throws Exception {
 
        br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N+1];
        int[][] dp = new int[N+1][2];
 
        for (int i = 0; i <N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        //dp[N][0] 은 한번에 한칸 올랐을 때
        //dp[N][1] 은 한번에 두칸 올랐을 때
        dp[0][0] = arr[0];
        dp[1][0] = dp[0][0]+ arr[1];
        dp[1][1] = arr[1];
        
        for(int i=2; i<N; i++){
            //이전에 두칸 올랐을때만 현재 한칸을 이동할 수 있다.
            //이전에 한칸 올랐다면 연속된 세칸을 밟을 경우가 생긴다.
            dp[i][0] = dp[i-1][1] + arr[i];
            
            //두칸을 이동할 경우 어떠한 제한조건이 없다. 두칸전 위치의 최대값과 현재값을 더해준다.
            dp[i][1] = Math.max(dp[i-2][0], dp[i-2][1])+arr[i];
        }
        System.out.println(Math.max(dp[N-1][0], dp[N-1][1]));
        
        
    }
}