계단 오르기



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



계단을 오르면 점수를 얻는다. 도착지점 까지 일련의 규칙으로 올라갈 때, 얻을 수 있는 최고점은 얼마일까?



도착지점에서 생각해보면, 이 지점에 오기 위해서는 두 계단 밑이나, 한 계단 밑에서 올라왔을 것이다.


또한 그 지점 자체의 최고점이 존재할 것이며, 그 최고점은 두 계단 밑이나 한 계단 밑에서 올라오면서 형성된다.


따라서 각 층마다 상태를 dp로 저장해서 풀면 되겠다.



유의할 점은 한계단씩 연속으로 두번 오를 수 없다는 점이다.


즉 한번 한 계단만 올랐으면, 다음엔 반드시 두 계단을 올라야 한다.


그러면 한 층에서 상태는 두가지로 나눠지고 O(n * 2) 안에 풀 수 있다.



함수 func(int floor, int cnt) = floor층이고, 한 계단씩 연속해서 cnt번 올라왔을 때 얻는 최고점수를 계산해줌.


다음 층으로 오를 때는 cnt = 1이라면 2층 오르는 상태로 이어지며,


cnt = 0 이라면 한 계단 오르거나 두 계단 오르는 상태로 분기된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <algorithm>
using namespace std;
 
 
#define M -987654321
 
 
int n;
int stair[301], dp[301][3];
 
 
int func(int floor, int cnt) {
    if (floor > n)
        return M;
 
    if (floor == n)
        return stair[n];
 
    int& ref = dp[floor][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(floor + 11+ stair[floor];
        int b = func(floor + 20+ stair[floor];
 
        return ref = max(a, b);
    }
    else if(cnt==1)
        return ref = func(floor + 20+ stair[floor];
}
 
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d"&stair[i]);
        for (int j = 0; j < 3++j)
            dp[i][j] = -1;
    }
 
    printf("%d", max(func(10), func(20)));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01
백준) 2342 Dance Dance Revolution  (0) 2017.09.21
백준) 2618 경찰차  (1) 2017.09.17

+ Recent posts