[ Algorithm ] 백준 2569번 : 계단 오르기 - [JAVA]

🎆백준 2569번 계단 오르기🎆

---

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/2579

🔍예제 입력

6
10
20
15
25
10
20

🔍예제 출력

75

---

📌풀이

🔍풀이 설명

다이나믹 프로그래밍(Dynamic Programming) 문제였다.

DP : 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.
각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. -> 계산 횟수를 줄일 수 있음
출처

문제의 조건을 다음과 같았다.

1. 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 밟아선 안 된다.
3. 마지막 계단은 반드시 밟아야 한다.

따라서 점수의 총점을 계산하는 식을 다음과 같이 세웠다.

sum[i] = Math.max(sum[i-3]+Stairs[i-1], sum[i-2]) + Stairs[i];

---

🔍코드

package Dynamic_Programming;

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

//계단 오르기
public class p2579 {
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int [] Stairs = new int[301];
        int [] sum = new int[301];

        for(int i=1; i<=N; i++){
            Stairs[i] = Integer.parseInt(br.readLine());
        }
        sum[1] = Stairs[1];
        sum[2] = Stairs[1] + Stairs[2];
        sum[3] = Math.max(Stairs[1], Stairs[2]) + Stairs[3];

        for (int i=4; i<=N; i++){
            //조건
            //1. 계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다.
            //2. 연속된 세 개의 계단을 밟아선 안 된다.
            //3. 마지막 계단은 반드시 밟아야 한다.
            // Math.max(3단계 전까지의 점수의 합과 1단계 이전의 계단 점수, 2단계 전까지의 합)
            // 마지막에는 마지막 계단의 점수를 무조건 더한다.
            sum[i] = Math.max(sum[i-3]+Stairs[i-1], sum[i-2]) + Stairs[i];
        }

        System.out.print(sum[N]);
    }
}

---

👋마무리👋

동적 계획법에 대한 이해는 하고 있었는데.. 조건을 활용하려니까 좀.. 어려웠던 것 같다.. 근데 손으로 5 ~ 6까지 수기로 계산해보면서 패턴을 찾는 방식으로 하니까 잘 풀리는 기분! .. 하지만 오래걸리긴 함!! ㅋㅎㅋㅎ 이것도 열심히 하다보면,, 늘겟지.. ㅠ_ㅠ 아자자