백준 알고리즘 | 2579 : 계단 오르기 (Python / 파이썬)

---

계단 오르기 성공출처분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	69152	23755	17427	36.247%

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

2579번: 계단 오르기

---

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

​

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

​

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

알고리즘 분류

다이나믹 프로그래밍

---

백준 알고리즘 # 2579번 : 계단 오르기

import sys
input = sys.stdin.readline

n = int(input())
max_score = [0 for _ in range(n)]

# [10, 20, 15, 25, 10, 20]
steps = []
for i in range(n):
    steps.append(int(input()))

def score(n):
    # 첫 번째 계단, 10
    max_score[0] = steps[0]
    if n == 1:
        return
    
    # 두 번째 계단의 최댓값은 두 계단 모두를 밟을 때, 30
    max_score[1] = steps[1] + steps[0]
    if n == 2:
        return

    # 세 번째 계단은 1, 3 vs 2, 3 중 큰 수, 25 vs 35
    max_score[2] = max(steps[0] + steps[2], steps[1] + steps[2])
    if n == 3:
        return
    for i in range(3, n):
        # 마지막에서 치면 전계단에서 도착했을 때와
        # 전전 계단에서 도착했을 때를 비교하면 됌
        max_score[i] = steps[i] + max(steps[i - 1] + max_score[i - 3], max_score[i - 2])

score(n)
print(max_score[n - 1])

풀이

문제 자체에 대해서 DP(다이나믹 프로그래밍)으로 푸는 방법을 알기 위해서 구글링을 했어요...ㅋㅋㅋㅋ

출처: https://daimhada.tistory.com/181

위 블로그에서 설명된 방식이 오늘의 key point 1라고 생각됩니다👏🏻

​

그래도 제가 이해한 바를 섞어서 풀이를 해보면

먼저 계속해서 런타임 오류가 나서

​

1. import sys 후에 sys.stdin.readline()을 써서 입력받았어요.

그 후 n 변수를 설정해서 계단의 개수를 입력받고

max_score 변수를 미리 설정하고 계단의 개수를 세어줄 steps 변수를 리스트로 초기화해두었어요.

다음으로 for문으로 각 계단의 값을 입력받아 steps에 추가(append)해주었습니다.

​

2. score를 def로 정의하고 n을 인자(argument)로 입력받아서 코드를 짰어요.

첫 번째 계단은 바로 max_score[0]에 해당이 되고

두 번째 계단부터 이제 첫 번째와 두 번째 계단을 더해준 값이 되고

​

세 번째 계단에는 첫 번째 계단에서 세번째 계단을 합친 값과

두 번째 계단과 세 번째 계단을 합친 값을 비교해서

더 큰 값을 max_score[2]로 초기화 시켰어요.

​

다음으로 for문을 통해서 세 번째 계단 다음 값들을 비교하는데

여기서 위 블로그에서 본 개념이 나와요.

​

key point 2

3. 마지막에 도착할 때, 전계단에서 도착했을 때의 값과 전전 계단에서 도착했을 때의 값을 비교하는 것!

max로 steps[i - 1] + max_score[i - 3]과 max_score[i - 2] 중에 더 큰 값을 비교해내고

steps[i]와 더해줘서 max_score[i]로 초기화시켜주면 끄-읏!

​

이제 이것을 score로 정의한 함수를 score(n)으로 불러주고

max_score[n - 1] 마지막까지 쭉 합쳐진 값을 불러오면 최댓값 75가 나오면서 문제 풀이가 끝납니다😂

​

DP 문제는 계속해서 풀어봐야겠어요...💪🏻

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏🏻

Python으로 푸는 백준 2579. 계단 오르기

 

wook2124/Algorithm-Test

최종 소스코드