[백준 2579번] 계단 오르기

문제 링크: 2579번 계단 오르기

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

 

s(n) = max( s(n - 2) + a(n), s(n - 3) + a(n - 1) + a(n) )의 식을 이용할 수 있다.

3개 계단을 연속해서 밟으면 안 된다는 조건을 고려해서, s(n -1)을 이용하지 않는 데에 초점을 두는 것이다.

 

C/CPP

#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int n, a[300], d[300];

int main(void) {
    scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &(a[i]));
    d[0] = a[0], d[1] = a[0] + a[1], d[2] = MAX(a[0] + a[2], a[1] + a[2]);
    for (int i = 3; i < n; i++) d[i] = MAX(d[i - 2], d[i - 3] + a[i - 1]) + a[i];
    printf("%d", d[n - 1]);
    return 0;
}

 

 

bottom-up 방식으로, 직전 계단을 밟았을 때, 밟지 않았을 때로 나누어 정답을 도출할 수도 있다.

 

Python

seq = 0
dis = 1

n = int(input())

steps = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    steps[i] = int(input())
sums = [[0, 0] for _ in range(n + 1)]

if n == 1:
    print(steps[1])
    exit(0)

if n == 2:
    print(steps[1] + steps[2])
    exit(0)

sums[1][seq] = steps[1]
sums[1][dis] = steps[1]
sums[2][seq] = steps[1] + steps[2]
sums[2][dis] = steps[2]

for i in range(3, n+1):
    # 직전 계단을 밟았을 때
    sums[i][seq] = sums[i - 1][dis] + steps[i]

    # 직전 계단을 밟지 않았을 때
    sums[i][dis] = max(sums[i - 2][seq], sums[i - 2][dis]) + steps[i]

print(max(sums[n][seq], sums[n][dis]))