[백준] 2579번 : 계단 오르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2579번: 계단 오르기

 

1. 문제 설명

2. 풀이과정

해당 문제는 이전에 밟은 계단의 결과에 따라 다음 밟을 수 있는 계단이 정해진다.

따라서 이전에 밟은 계단의 결과를 활용하여 문제를 해결하는 다이나믹 알고리즘을 사용해야 한다.

계단은 1칸 올라가거나 2칸을 바로 올라갈 수 있지만 1칸씩 3칸을 연속으로 밟을 수 없다. 하여 계단 3칸을 확인해 다음 계단을 선택해야 한다.

3칸의 계단을 봤을 때 계단을 올라가는 경우는 1칸을 올라간 뒤, 2칸을 올라가는 방법과 2칸을 올라간 뒤, 1칸을 올라가는 방법이 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 계단의 개수를 입력받는다. T = int(sys.stdin.readline())
3. 계단의 점수를 저장할 리스트를 생성한다. score = list()
4. 계단의 수만큼 반복하며 for _ in range(T)
5. 각 계단의 점수를 입력받아 리스트에 추가한다. score.append(int(sys.stdin.readline()))
6. 만약 계단이 1개라면 if (len(score) <= 1)
7. 해당 계단의 점수를 출력한다. print(score[0])
8. 반면에 계단의 개수가 2개 이상이면 else
9. 먼저 이전 계단까지 최고의 점수를 저장할 리스트를 생성하고 0으로 초기화한다. step = [0] * T
10. 처음에는 1칸을 가는 경우를 저장한다. step[0] = score[0]
11. 그다음으로는 1칸을 2번 연속으로 가는 경우를 저장한다. step[1] = score[0] + score[1]
12. 다음 3번째 계단부터는 다이나믹 알고리즘을 활용하는데 다음 계단의 인덱스 값부터 끝까지 반복하며 다음 계단의 최적의 경우를 계산한다. for i in range(2, T)
13. 먼저 1칸을 올라가고 2칸을 올라가는 경우의 점수를 계산한다. next = step[i - 2] + score[i]
14. 다음으로 2칸을 올라가고 1칸을 올라가는 경우의 점수를 계산한다. jump = step[i - 3] + score[i - 1] + score[i]
15. 여기서 step[i - 3]은 0이므로 더해줘도 상관없다. 이는 i가 3일 때부터를 위한 식이다.
16. 다음 계단은 위 2가지 경우 중 더 높은 점수를 얻을 수 있는 경우를 저장한다. step[i] = max(next, jump)
17. 모든 계단을 올라가면, 마지막 계단을 올라갈 때 최적의 점수를 출력한다. print(step[-1])

반응형

3. 소스코드

import sys

T = int(sys.stdin.readline())

score = list()
for _ in range(T):
    score.append(int(sys.stdin.readline()))

if (len(score) <= 1):
    print(score[0])
else:
    step = [0] * T
    step[0] = score[0]
    step[1] = score[0] + score[1]
    for i in range(2, T):
        next = step[i - 2] + score[i]
        jump = step[i - 3] + score[i - 1] + score[i]

        step[i] = max(next, jump)

    print(step[-1])