백준 2579번 계단 오르기 S3 - DP

 

2006도 초등부 문제라니.. 껄껄

점화식을 고려해 봅시다.

 

한번에 한 계단 또는 두 계단씩 오를 수 있지만 연속된 계단 3개는 밟을 수 없으며 마지막은 무조건 밟아야한다.

점화식은 이번에 놓을 위치에는 무조건 딛고, 그 전 경우에서 Math.max로 더 큰값을 정해주었다.

예시

 

가장 높은곳인 6에 놓을때는 dp [3] + arr [5] + arr [6] 랑 dp[4] + arr[6]중 큰 값을 가져가면 되겠다.

 

import java.util.*;
 
public class Main { // 백준 2579 계단 오르기 실3
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer = 0;
        int N = sc.nextInt();
        int  arr[] = new int[N + 1];
        int dp[] = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
        
        dp[0] = 0;
        if(N >= 1) { // N이 300이하이므로 1~3이 하드코딩이라 범위 초과. 기억할것.
            dp[1] = arr[1];
        }
        if(N>=2) {
            dp[2] = arr[1] + arr[2];
        }
        if(N>=3) {
            dp[3] = Math.max((arr[1] + arr[3]), (arr[2] + arr[3]));
        }
        
 
        for (int i = 4; i <= N; i++) {
            dp[i] = Math.max((arr[i] + dp[i-2]),(arr[i] + arr[i-1] + dp[i-3]));
        }
        System.out.println(dp[N]);
    }
}

 

다만 3까지는 하드코딩 해주어 오류를 없애주었다.

 

에라이~