[백준]2579번 계단 오르기(java)

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

2579번: 계단 오르기

백준 2579번 계단 오르기 문제 링크입니다.

핵심

계단을 1칸, 2칸 이동 가능하다. 마지막 계단은 반드시 밟아야 한다. 3개 연속으로 계단은 올라갈 수 없다.

가장 중요한 것이 3개의 계단을 연속으로 올라갈 수 없다는 것이다. 

정답 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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[1] = arr[1];
        if(n>=2) dp[2] = arr[1]+ arr[2];
        for (int i =3; i<=n; i++){
            dp[i] = Math.max(dp[i-2],dp[i-3]+arr[i-1])+arr[i];
        }
        System.out.println(dp[n]);
    }
}

해설

dp는 해당 계단까지 최대의 값이다. arr와 dp는 보기 편하게 i=1부터 시작한다.

n=2일 때 가장 큰 값은 첫 번째 계단과 두 번째 계단을 더하는 것이다.

n=3 이후부터는 3개 연속으로 올라가는 경우를 제거해야 한다. 

for문을 보면, dp [i-2]와 dp [i-3]+arr [i-1]의 값을 비교하여 둘 중 큰 값에 arr [i] 값을 더하여 dp [i]를 만든다.이는 해석해보면 dp [i-2]을 경우 만약 계단이 4층이라 하면 2층과 4층을 밟았다는 것이다.반대로 dp [i-3]+arr [i-1]의 경우는 4층이라 하면 1층과 3층, 4층을 밟았다는 것이다.이러한 식은 3개 연속으로 올라가는 것을 막아준다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.