백준 - 2579 계단 오르기(Java)

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

2579번: 계단 오르기

 

간단하면서, 대표적인 DP 문제입니다.

계단을 조건에 맞게 밟으면서 움직여야 합니다.

조건은 다음과 같습니다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

즉, 그림으로 표현하면 다음과 같습니다.

세 개의 연속된 계단을 밟을 수 없기 때문에 위와 같은 그림이 그려질 수 있습니다.

그림에서 표현했다 싶이 i-2번째를 밟느냐, 밟지 않느냐에 따라 두 가지 조건을 비교하면 됩니다.

i-2 번째를 밟으면 i 번째에 가기 위해 i-1은 밟으면 안됩니다.(문제 조건에 의해 연속된 세 개의 계단을 밟을 수 없습니다)

i-2 번째를 밟지 않으면 i 번째에 가기 위해 i-3번 째의 최대와 i-1를 밟으면 됩니다.

 

따라서 점화식은 다음과 같습니다.

dp[i] = max(dp[i-2], dp[i-3]+stair[i-1]) + stair[i]

 

[구현 코드]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] stairs = new int[n+10]; // 넉넉히 배열 선언 해 줘야됨
        int[] dp = new int[n+10];

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

        dp[1] = stairs[1];
        dp[2] = stairs[2] + dp[1];

        for(int i=3; i<n+1; i++){
            dp[i] = Math.max(dp[i-3]+stairs[i-1], dp[i-2]) + stairs[i];
        }

        bw.write(String.valueOf(dp[n]));

        bw.flush();
        bw.close();
        br.close();
    }
}