[BOJ] 2579. 계단 오르기(DP)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 

- 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

- 마지막 도착 계단은 반드시 밟아야 한다.

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제는 포도주 시식 문제와 같은 로직의 문제이다.

포도주 시식 문제와 동일하게

DP[N}은 N까지의 계단에서 얻을 수 있는 총 점수의 최댓값이다.

다만 여기서는 마지막 도착 계단은 반드시 밟아야 한다는 조건이 있다.

그렇기 때문에 두 가지 경우로 나눌 수 있다.

1. N번째 계단이 연속 1번째 계단일 경우

DP[N-2] + A[N]

2. N번째 계단이 연속 2번째 계단일 경우

DP[N-3] + A[N-1] + A[N]

즉, DP[N]는 max(DP[N-2] + A[N], DP[N-3] + A[N-1] + A[N]) 라는 점화식을 세울 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <cstdio> int max(int p, int q) { return p > q ? p : q; } int A[301], DP[301]; int main(void) {     int n, i, res = 0;     // freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         scanf("%d", &A[i]);         DP[i] = max(DP[i - 2], DP[i - 3] + A[i - 1]) + A[i];     }          printf("%d\n", DP[n]);       return 0; } Colored by Color Scripter

cs