[백준] 2579번 계단 오르기 파이썬

다이나믹 프로그래밍 유형의 문제 중에서 선택했다.

<규칙>

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

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

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

각 계단에 쓰여 있는 점수의 최대합을 구하자.

 

2579번 계단 오르기

[시도1] 맞았습니다!! with 솔루션

n = int(input())

score = [0] #계단 점수 저장
dp = [0] #각 층까지의 최대 점수 저장

for i in range(n):
  score.append(int(input()))

if n == 1:
  dp.append(score[1])
elif n == 2:
  dp.append(score[1])
  dp.append(dp[1] + score[2])
else:
  dp.append(score[1])
  dp.append(dp[1] + score[2])
  for i in range(3, n+1):
    dp.append(max( dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i]))

print(dp[n])

 

규칙에 따라서 마지막 계단은 반드시 밟아야 한다.

마지막 계단을 밟기 전에 

1. 마지막 계단 바로 전의 계단을 밟기 =>  마지막 계단 전전의 계단은 밟을 수 없음. (∵연속 3개의 계단을 밟을 수 없으므로)

2. 마지막 계단 바로 전의 계단을 밟지 않기 => 마지막 계단 전전의 계단을 이미 밟음. (∵ 한 번에 한 계단 또는 두 계단 씩 오를 수 있는데 전의 계단을 밟지 않았으니 전전의 계단은 밟았어야 하므로)

 

[점화식]

1. dp[n-3] + score[n-1] + score[n]

2. dp[n-2] + score[n]

이 두 가지 경우의 최댓값을 구해야 한다.

=> dp[n] = max( dp[n-3] + score[n-1] + score[n], dp[n-2] + score[n] )

단, 위 식은 n이 3일 때부터 가능하므로 n이 0, 1, 2일 때는 따로 처리해준다.

 

0인 경우에는 그냥 0 값으로 맨 처음에 변수 생성 시에 정해두었다.

1과 2일 때에는 각각 1층과 1층+2층의 점수가 최댓값이 되므로 해당 점수를 고려해 주었다.

3부터는 점화식을 활용한다.

 

보통은 DP 문제를 풀 때에 함수를 활용하는데 아직 나는 함수가 낯설다...!

그래도 앞으로는 함수를 상황에 맞게 잘 사용할 줄 알아야 할 것 같다.

 

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

2579번: 계단 오르기