87. 백준 2579 번 Python 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 알고리즘 문제인 BOJ 2579 번 계단 오르기 입니다.

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

2579번: 계단 오르기

 

 

백준 2579 번 Python 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
stair = [int(input()) for _ in range(N)]

sum = 0
if N <= 2:
    for i in range(N):
        sum += stair[i]
    print(sum)

else:
    dp = []
    dp.append(stair[0])
    dp.append(stair[0] + stair[1])
    dp.append(max(stair[2] + stair[0], stair[2] + stair[1]))

    for i in range(3, N):
        dp.append(max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]))
    print(dp[N-1])

 

문제 요약

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
   즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

총 3가지의 규칙을 지키면서 계단을 밟으면서 생기는 최대 점수를 구하는 문제입니다.

 

문제 접근

지금까지의 계단 점수 중 위의 조건을 지키면서 가장 높은 점수들을 저장했다고 가정한다면

 

마지막 도착 계단을 E 라고 했을 때, 계단은 한칸 or 두칸을 지날 수 있으므로

E를 밟기위해서는 E - 1 혹은 E - 2 계단 중 더 높은 점수를 가진 계단을 밟으면 되는데

 

1. 만약 [ E - 2 ] 계단이 점수가 더 높다면 E - 2의 계단을 밟아주면 되고

 

2. 만약 [ E - 1 ] 계단이 점수가 더 높다면 다음 계단은 1칸만 오를 수 있으므로

[ E - 2 ] 를 밟지 않고 얻은 [ E - 1 ] 까지의 계단 점수를 구해서 더해주면 됩니다.

즉 [E - 3] + [E -1] 이 되겠죠 (1칸 아니면 2칸으로 이동 가능)

 

Python 코드 구현

먼저 계단의 모든 점수들을 입력받아 저장합니다.

stair = [int(input()) for _ in range(N)]

 

그리고 i번째 계단 까지의 누적 최대 점수를 저장할 리스트인 dp 를 선언하고,

 Base Case를 작성합니다. 앞서 우리가 구한 공식에서 i 번 째 계단을 구하기 위해 i - 3 까지 사용했으므로

i 를 식으로 구하기 위해서는 i - 3 까지가 저장되어야 있어야 됩니다.

 즉 최소 3개의 Base Case 가 필요합니다.

0번 계단까지의 최대 누적 점수는 stair[0]

1번 계단까지의 최대 누적 점수 = stair[0] + stair[1]

2번 계단까지의 최대 누적 점수 = max(stair[2] + stair[0], stair[2] + stair[1])

dp = []
dp.append(stair[0])
dp.append(stair[0] + stair[1])
dp.append(max(stair[2] + stair[0], stair[2] + stair[1]))

 

그리고 사전에 구한 공식을 적용하여 i번째 계단까지의 최대 누적 점수를 계산합니다.

for i in range(3, N):
    dp.append(max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]))

 

이제 출력하면 됩니다.

print(dp[N-1])

 

이 문제에서는 N에 대한 범위가 나와있지 않으므로, 예외처리를 해줍시다.

N <= 2 일때 BASE CASE를 만들지 않고, 그냥 더해서 출력하는 식으로 구현했습니다.

sum = 0
if N <= 2:
    for i in range(N):
        sum += stair[i]
    print(sum)

 

백준 2579 번 계단 오르기 Python 최종 코드입니다.

N = int(input())
stair = [int(input()) for _ in range(N)]

sum = 0
if N <= 2:
    for i in range(N):
        sum += stair[i]
    print(sum)

else:
    dp = []
    dp.append(stair[0])
    dp.append(stair[0] + stair[1])
    dp.append(max(stair[2] + stair[0], stair[2] + stair[1]))

    for i in range(3, N):
        dp.append(max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]))
    print(dp[N-1])

 

백준 2579 번 계단 오르기 자세한 설명 및 Python 코드였습니다.

감사합니다.