(Python/🥈3) 백준 알고리즘 2579번: 계단 오르기

728x90

문제 출처: https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

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

www.acmicpc.net

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(input())

dp = [0] * 301
arr = [0]*301
for i in range(N):
    arr[i] = int(input())

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2])
for i in range(3,N):
    dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i])
print(dp[N-1])

for i in range(3,N):
    dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i])

마지막 지점도 밟는거로 한다.

인덱스는 0 부터 했을때

만약 인덱스 3의 최댓값을 알고 싶을때는

1). 0 > 1 > 3

2). 0 > 2 > 3

3). 1 > 3

1) 이랑 3) 동선이 겹친다 >> 도착지 인덱스 이전값과, 인덱스 전전값의 최댓값을 넣어주면 된다.

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


N = int(input())

dp = [0] * 301
arr = [int(input()) for i in range(N)]
if N == 1:
    print(arr[0])
elif N == 2:
    print(arr[0]+arr[1])
else:
    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    dp[2] = max(arr[0]+arr[2], arr[1]+arr[2])
    for i in range(3,N):
        dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i])
    print(dp[N-1])