[백준 2579번] 계단 오르기 - JAVA

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

2579번: 계단 오르기

풀이

사용한 알고리즘: 다이나믹 프로그래밍

 

풀이전략

마지막 계단을 반드시 밟아야하므로 방법은 2가지로 나뉜다.

1. 마지막에서 2번째 전 계단을 밟고 마지막 계단을 밟는 경우

2. 마지막에서 바로 전 계단을 밟고 마지막 계단을 밟는 경우

 

하지만 2번의 경우에는 전전 계단을 밟았을 가능성이 있다.

이를 피하기 위해 수정을 하면

(수정후) 2. 마지막에서 3번째 전 계단을 밟고, 마지막 직전 계단과 마지막 계단을 밟는 경우

로 수정할 수 있다.

 

따라서 d[i]에 i 번째 계단을 마지막일 때 가장 최대의 점수를 저장하고

graph[i]를 i 번째 계단의 점수를 뜻할 때, 식은

d[i]=Math.max(d[i-3]+stairs[i-1]+stairs[i],d[i-2]+stairs[i]) 가 된다.

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int stairs[] = new int[N+1];

        for(int i=1;i<N+1;++i){
            stairs[i]=Integer.parseInt(br.readLine());
        }

        int d[]= new int[301];
        if(N>=1) d[1]=stairs[1];
        if(N>=2) d[2]=stairs[1]+stairs[2];
        for(int i=3;i<N+1;++i){
            d[i]=Math.max(d[i-3]+stairs[i-1]+stairs[i],d[i-2]+stairs[i]);
        }
        System.out.println(d[N]);
    }
}