DevelopmentAlgorithm

ACMICPC - 계단 오르기(2579)

Algorithm

계단 오르기

스티커 문제와 비슷한 느낌이다. 해당 계단을 포함해서 오르느냐 안오르냐로 나누어서 생각했다.

만약 N번째 계단을 선택하지 않는다면 2칸을 한번에 건너뛸 수 없으므로 N-1번째 계단은 반드시 선택해야 한다.

N번째 계단을 선택한다면 이렇게 두 가지 경우가 있다.

  1. N-1번째 계단을 오르고, N-2번째 계단을 오르지 않아야 한다. (연속된 세 개의 계단을 오를 수 없음)
  2. N-1번째 계단을 오르지 않는다.

이 두가지를 고려해서 선택하는 것을 [1], 선택하지 않는것을 [0]에 담는다고 하자.
D[N][0]에는 항상 D[N-1][1]이 들어가게 될 것이고, D[N][1]은 두 가지의 경우의 수가 있으므로 둘 중에 큰 값을 고른다음 자신의 계단을 선택한 만큼 더해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N = input()
A = []
for i in range(N):
    A.append(input())

D = [[0] * 2 for i in range(N)]
D[0][1] = A[0]
D[1][0] = D[0][1]
D[1][1] = D[0][1] + A[1]

for i in xrange(2, N):
    D[i][0] = D[i - 1][1]
    D[i][1] = max(D[i - 1][0], D[i - 2][0] + A[i - 1]) + A[i]

print D[N - 1][1]

이제 슬슬 개강도 다가오고 다른것들도 할거리가 생겼으니 많이는 못풀겠지만 꾸준하게 하루에 하나라도 풀어봐야겠다.

Share