[백준] 2579 : 계단 오르기 (JAVA/자바)

문제

BOJ 2579 : 계단 오르기 - https://www.acmicpc.net/problem/2579

풀이

[조건]

1. 계단은 한 번에 한 계단, 두 계단씩만 오를 수 있다
2. 연속된 3개의 계단을 밟으면 안된다

위 조건을 잘 보고 점화식을 세우면 된다. n의 위치에서 다음과 같은 경우의 수가 생길 수 있다.

(출처 : https://girawhale.tistory.com/3)

그래서 점화식 => dp[i] = Math.max(dp[n-3] + stairs[n-1], dp[n-2]) + stairs[n] 이 된다!

n이 1일 경우, 2일 경우, 3일 경우는 따로 예외처리 해주어야 한다.

코드

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; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[n + 1];
        dp[1] = stairs[1];

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

        System.out.println(dp[n]);
    }
}

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 3

🤦‍♀️ 오늘의 메모

• 포도주 시식 문제랑 같은 문제라고 생각했는데, 현재 위치의 계단을 밟지 않는 경우는 생각하지 않아도 되기 때문에 OXO와 XOO의 경우만 확인하면 된다! 문제를 잘 이해해보장

• 실버 3의 난이도를 가짐에도 나는 여전히 dp가 어렵다,,,ㅠ
  
  
  

참고 사이트

https://girawhale.tistory.com/3