자바(백준) 2579 계단 오르기 (다른 풀이)

오답 노트 & 새로 알게 된 점

전에 풀었던 문제는 일차원 배열로 해결했다. 이번에는 이차원 배열을 이용하였다.

 

해당 문제는 강의를 통해 풀었던 문제이다.

이런 생각은 어떻게 할까,,, 라는 생각이 들었던 문제이다.

 

dp[i][0]은 i-1번째 계단을 밟지 않고 i번째 계단을 밟을 경우,

dp[i][1]은 i-1번째 계단을 밝고 i 번째 계단을 밟을 경우이다.

 

그래서 dp[i][0]을 구하기 위해서는

i-1번째 계단을 밟지 않을 경우에는 연속 세 계단을 어차피 오를 수 없기 때문에 

dp[i-2][0]과 dp[i-2][1]중 최댓값을 고르면 된다.

 

dp[i][1]은 i-1번째 계단을 밟을 경우이므로, i-2번째 계단을 밟으면 안 된다.

그래서 dp[i-1]계단에서 i-2계단을 밟지 않아야 하므로, dp[i-1][1]에서 arr[i]을 더하면 된다.

 

---

 

코드

package Dynamic_Programming;
 
import java.io.*;
 
public class BOJ2579_2{
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int size = atoi(br.readLine());
        int arr[] = new int[size+1];
 
        for (int i = 1; i <= size; i++) {
            arr[i] = atoi(br.readLine());
        }
 
        int dp[][] = new int[size+1][2];
 
        dp[1][0] = 0;
        dp[1][1] = arr[1];
 
        if (size >= 2) {
            dp[2][0] = arr[2];
            dp[2][1] = arr[1] + arr[2];
        }
 
        for (int i = 3; i <= size; i++) {
            dp[i][0] = Math.max(dp[i - 2][0], dp[i - 2][1]) + arr[i];
            dp[i][1] = dp[i - 1][0] + arr[i];
        }
 
        System.out.println(Math.max(dp[size][0], dp[size][1]));
    }
}