[Python] 백준 2579번: 계단 오르기 풀이

 

소스코드 1

n = int(input())
A = [[0] for _ in range(n)]
dp = [[0]* 3 for _ in range (n)]
for k in range(n):
    A[k] = int(input())
dp[0][1] = A[0]
for i in range(1,n) :
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = dp[i-1][0] + A[i]
    dp[i][2] = dp[i-1][1] + A[i]
print(max(dp[n-1][1], dp[n-1][2]))
    

 

저번에 풀었던 와인 문제와 비슷한 원리이다.

각 계단에 대해서 연속으로 0번 밟았을 때, 연속 1번 밟았을 때, 연속 2번 밟았을 때 총 3가지 경우로 나눠보았다.

이렇게 2차원 배열을 이용해서 푸는 방법이 첫 번째 소스코드이다.

 

소스코드2

n = int(input())
A = [0 for _ in range(n+2)]
dp = [0 for _ in range (n+2)]
for k in range(n):
    A[k] = int(input())
dp[0] = A[0]
dp[1] = A[0] + A[1]
dp[2] = max(A[0] + A[2] ,A[1] + A[2])
for i in range(3,n) :
    dp[i] = max (dp[i-2] + A[i],dp[i-3] + A[i-1] + A[i] )
print(dp[n-1])
    

 

사실 소스코드1과 다른 점은 거의 없다. 다만 2차원 배열을 굳이 쓰지 않아도 된다는 점에서 이 코드가 더 간편하다.

dp[i-2] + A[i] 는 전전칸을 밟고 전 칸을 밟지 않고 i번째 칸을 밟는 경우이다.

dp[i-3] + A[i-1] + A[i] 는 전 칸을 밟고 i번째 칸을 밟는 경우인데,

만약 dp[i-1] + A[i] 라고 하면 연속 세 칸을 밟는 경우가 포함될 수도 있다. 왜냐하면 dp[i-1] 은 i-1 계단까지의 최댓값인데 i-1 의 전 칸인 i-2 칸을 밟았을 수도 있기 때문이다.

따라서 dp[i-3] 까지의 최댓값 + A[i-1] + A[i] 로 계단의 값은 수동으로 더해주면 된다.