[백준] 2579 계단 오르기

www.acmicpc.net/problem/2579

2579번: 계단 오르기

2020-11-10

 

---

import java.util.Scanner;

public class Main2579 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[] = new int[301];
        for(int i = 0; i <  N; i++) {
            arr[i] = sc.nextInt();
        }
        int dp[][] = new int[301][2];
            dp[0][0] = arr[0];
            dp[0][1] = arr[0];
            
            dp[1][0] = arr[1] + dp[0][0];
            dp[1][1] = arr[1];

        for(int i = 2; i < N; i++) {
            dp[i][0] = arr[i] + dp[i-1][1];
            dp[i][1] = arr[i] + Math.max(dp[i-2][0], dp[i-2][1]);
        }
        System.out.println(Math.max(dp[N-1][0], dp[N-1][1]));
    }
}

1. arr에 각 계단의 점수를 저장해둔다.

 

2. dp를 2차원 배열로 지정하고 0인 경우는 그 전 계단을 밟은 경우, 1인 경우는 그 전 전 계단을 밟은 경우로 정의했다.

 

3. 계단 2번 값 부터 점화식으로 계산을 한다.

 

(1) 현재 계단에서 그 전 계단을 밟는 경우는 현재 계단의 점수 값에 그 전 계단까지 계산한 값을 더한다.

dp[i][0] = arr[i] + dp[i-1][1];

(2) 현재 계단에서 전 전 계단을 밟는 경우는 현재 계단의 점수에 두 계단 전에서 그 전 계단을 밟았는지 아닌지 중에 더 큰 값을 더한다.

 

4. 마지막 꼭대기에서 그 전 계단을 밟았을 때까지의 총 값과 그 전 전 계단을 밟았을 때까지의 총 값 중 큰 값을 출력한다.