[BOJ] 2579번 계단 오르기 / 사용언어 : 파이썬(python)

※ 문제링크

2579번: 계단 오르기

해당 문제는 동적 프로그래밍을 적용하여 푸는 문제였다. 규칙을 찾기는 어려웠지만, 규칙을 알고나니 구현하는 것은

생각보다 어렵지 않았다. 문제를 푸는데 사용한 구체적인 방법과 코드는 아래와 같다.

<풀이방법>

- 1번째 계단에서 가질 수 있는 최댓값은 자기 자신과 동일 / 2번째는 1번째 계단과 2번째 계단의 합과 동일

- 3번째 계단이 가질 수 있는 최댓값 : 1번째 계단과 3번째 계단을 더한 값과 2번째 계단과 3번째 계단을 더한값 중 큰 값

- 4번째부터는 2개의 값을 지속적으로 비교하여 값을 추출 : 

   max(i-2의 최댓값(dp) + i의 값(num), i-3의 최댓값(dp) + i-1의 값(num) + i의 값(num))

1. 계단마다 가지는 값들 저장할 리스트와 해당 계단의 층수에서 가질 수 있는 최댓값을 저장할 dp리스트를 생성한다.

2. 규칙을 적용하여 반복문을 돌린 후 dp에서 마지막 값을 출력

+ 원소의 갯수가 3이하일 경우에는 조건문을 걸어서 처리해주어야 IndexError가 나지 않습니다.

 

N = int(input())
num_list = [int(input()) for _ in range(N)]
dp = [0 for _ in range(N)]

if N < 2:
    dp[0] = num_list[0]
elif N < 3:
    dp[0] = num_list[0]
    dp[1] = num_list[0] + num_list[1]
else:
    dp[0] = num_list[0]
    dp[1] = num_list[0] + num_list[1]
    dp[2] = max(dp[0] + num_list[2], num_list[1] + num_list[2])
    for i in range(3, N):
        dp[i] = max(dp[i-2] + num_list[i], dp[i-3] + num_list[i-1] + num_list[i])
print(dp[-1])

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.