[백준 BOJ_2579] 계단 오르기 Python 풀이

출처: 백준 온라인 저지

문제

풀이

주어진 조건을 예시 input으로 이해해 보았습니다.

# stairs = [10, 20, 15, 25, 10, 20]

1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
   • Start $ \rightarrow $ stairs[0] (O)
   • Start $ \rightarrow $ stairs[1] (O) (stairs[0]을 스킵)
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 시작점은 계단에 포함되지 않는다.
   • stairs[0] $ \rightarrow $ stairs[1] $ \rightarrow $ stairs[2] (X)
   • stairs[0] $ \rightarrow $ stairs[1] $ \rightarrow $ stairs[3] (O)
   • Start $ \rightarrow $ stairs[0] $ \rightarrow $ start[1] (O)
3. 마지막 도착 계단은 반드시 밟아야 한다.
   • 다른 말로 하면 반드시 마지막 계단에서 끝나야 한다.
   • stairs[4] $ \rightarrow $ Finish (X)
   • stairs[4] $ \rightarrow $ stairs[5] (O)

동적계획법으로 풀어 보겠습니다.

cache의 format은 다음과 같습니다.

# cache[N-1][0 or 1]
cache[N-1][0]: N-1번째를 밟지 않고 N번째를 밟을 때의 최대합
cache[N-1][1]: N-1번째를 밟고 N번째를 밟을 때의 최대합

한 번에 두 계단씩 오를 수도 있기 때문에, 직전의 계단을 밟을 수도, 밟지 않을 수도 있습니다. 두 가지의 경우를 모두 고려해주어야 합니다.

첫 번째 계단의 경우(cache[0]), 시작점의 값이 없기 때문에 그냥 cache[0][0]에 첫 번째 계단의 값(stairs[0])을 저장해주었습니다.

두 번째 계단(cache[1])은 첫 번째 계단을 밟지 않는 경우(cache[1][0])에는 자기 자신(stairs[1])의 값을, 첫 번째 계단을 밟는 경우(cache[1][1])에는 앞서 저장해 둔 첫 번째 계단의 값(cache[0][0])과 자기 자신(stairs[1])을 더해준 값을 저장해줍니다.

• 위에 두 번째 조건에서 언급했듯이 시작점은 계단에 포함되지 않기 때문에 두 번째 계단의 값은 첫 번째 계단을 아무런 조건 없이 포함할 수 있습니다.

세 번째 계단부터 조건이 달라집니다. for loop을 2(세 번째 계단)부터 N까지 돌려줍니다.

• cache[i][0] = max(cache[i-2]) + stairs[i]
  • N-1번째를 밟지 않는 경우(cache[i][0])에는 N-2번째 계단(cache[i-2])의 두 가지 경우 중 최대합이 큰 것을 선택해 자기 자신(stairs[i])과 더해준 값을 저장해줍니다.
• cache[i][1] = cache[i-1][0] + stairs[i]
  • N-1번째를 밟는 경우(cache[i][1])에는 N-1번째 계단(cache[i-2])의 두 가지 경우 중 N-2번째 계단을 밟지 않은 경우(cache[i-1][0])와 자기 자신(stairs[i])과 더해준 값을 저장해줍니다.
  • N-2번째를 밟고, N-1번째를 밟는 경우(cache[i-1][1])는 이어서 N번째를 밟게 되면 연속된 세 계단을 모두 밟게 되기 때문에 제외해주어야 합니다.

마지막으로 마지막 계단(cache[N-1])의 최대합 중 가장 큰 것을 골라 출력해줍니다.

다른 동적계획법 문제에서는 0과 1로 기록을 할 때, 자기 자신을 포함하지 않거나(cache[N-1][0]), 포함하는 경우(cache[N-1][1])로 기록을 하기도 하는데, 이 문제에서는 꼭 마지막 계단은 포함해야 한다는 조건 때문에 자기 자신을 포함한다는 가정하에 기록해준 것입니다.

코드

N = int(input())
stairs = [int(input()) for _ in range(N)]
cache = [[0 for _ in range(2)] for _ in range(N)]
cache[0][0] = stairs[0]
if N > 1:
    cache[1][0] = stairs[1]
    cache[1][1] = cache[0][0] + stairs[1]
    for i in range(2,N):
        cache[i][0] = max(cache[i-2]) + stairs[i]
        cache[i][1] = cache[i-1][0] + stairs[i]
print(max(cache[N-1]))