백준-2579-계단 오르기

1. 문제

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

2579번: 계단 오르기

2. 해결법

n번째 계단으로 마무리 해야 하므로 각 계단에 도착했을 때 나올 수 있는 경우는 2가지이다.

1. n-2 번째 계단을 들린 후 오는 경우 

2. n-3 , n-1번째 계단을 들린 후 오는 경우

두가지중 최대값을 선택하면 된다.

 

이를 코드로 나타내면 다음과 같다.

# dp = 지난 계단의 정수 합을 저장하는 배열
# stairs = 각 계단에 적힌 정수값
dp[i] = (stairs[i]+ max((stairs[i-1] + dp[i-3]) ,dp[i-2]))

 

이 때 n이 1 또는2일 때는 다 지나는 것이 최대값이기 때문에  따로 if문을 통해 계산해 주어야한다. 

위를 토대로 작성한 전체 코드는 다음과 같다.

import sys
# 계단의 수
n = int(sys.stdin.readline())
# 시작계단을 0으로 둔다.
stairs = [0]

for _ in range(n):
    stairs.append(int(sys.stdin.readline()))
# 시작 계단을 포함해서 n+1개 이다. 
dp = [0] * (n+1)

# n = 1,2일때는 바로 출력한다.
if n == 1 : 
    print(stairs[1])
elif n==2:
    print(stairs[2] + stairs[1])
# n=3일 때 부터 다음과 같은 규칙이 적용된다.
else:
    dp[1] = stairs[1]
    dp[2] = stairs[1] + stairs[2]
    dp[3] = stairs[3] + max(stairs[1],stairs[2])

    for i in range(4 , n+1):
    	# i번째 계단에 도착할 때 최대값은 해당 계단값에 2칸 전의 최대값 또는 1칸 전의
        # 최대값+ 전칸값 중 더 큰값이 된다.
        dp[i] = (stairs[i]+ max((stairs[i-1] + dp[i-3]) ,dp[i-2]))     
    print(dp[n])