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

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

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에서 위치한 도착지점까지 가는 게임이다.

각 계단에는 일정한 점수가 쓰여 있고 그 계단을 밝으면 점수를 얻게 된다.

이때 총점수의 최댓값을 구해야 하면 아래의 규칙을 지켜야 한다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

위그림의 예를 가지고 풀어본다면

첫 번째 계단 => 두 번째 계단 => 네 번째 계단 => 다섯 번째 계단 밟으면 최댓값이 나온다.

 

 풀이

이 문제를 풀기 위해서 해야 할 첫 번째 생각은 무조건 마지막 계단을 밟아야 하는 조건이 가장 중요하다.

시작 지점부터 시작하는 것보다는 무조건 마지막 지점을 밟아야 하기에 마지막 계단을 기준으로 계산하면 좀 더 편하게 생각할 수 있다.

그다음으로는 마지막 계단까지 가기 위해서 한 번에 한 계단씩 또는 두 계단씩 오를 수 있으면 연속된 세 개의 계단을 밟을 수는 없다는 조건을 생각하면서 문제플 푸는 점화식을 완성해야 한다.

 

위 그림을 예로 든다면

마지막 계단 다섯 번째 계단을 밟았을 때 총점수가 dp [5]라 하자  =>(dp는 n번째 계단까지 밟은 점수 총점)

그럼 마지막 계단을 밟는 경우의 수를 생각해 보면

dp [4]+ 다섯 번째 계단

dp [3]+ 다섯 번째 계단

이렇게 2가지 경우수가 있는데 위 조건에서 연속으로 한 칸씩 세 번을 넘어가지 못하는 조건이 있기에

dp [4]+ 다섯 번째 계단 => dp [2] + 네 번째 계단 + 다섯 번째 계단 

 

최종적으로는

dp[2] + 네번째 계단 + 다섯번째 계단 =dp [5]

dp [3]+ 다섯 번째 계단 =dp [5]

 

이렇게 2가지 식이 나오는 것을 알 수 있다 이것을 일반식으로 바꾼다면

dp [n]=dp [n-3]+(n번째 계단)+(n-1번째 계단)

dp [n]=dp [n-2]+(n번째 계단)

이 되면 이때 최댓값이 필요함으로 위 두식의 최댓값을 고를 수 있도록 코드를 짜면 된다.

 

그리고 이제 초기값이 필요한다 

만약 계단이 2개만 있는 경우 위의 식을 적용하지 못한다 그렇기에 초기값 설정을 해줘야 한다.

dp [n]=dp [n-3]+(n번째 계단)+(n-1번째 계단) 식을 보면 4번째부터 이식을 적용할 수 있다.

dp [1]=1번 계단

dp [2]=1번 계단 +2번 계단

dp [3]= max( 2번 계단+3번 계단 , 1번 계단+3번 계단 )

 

코드

n=int(input())
array=[0]
dp=[0]*301

for i in range(n):
    a=int(input())
    array.append(a)
    if i==0:
        dp[1]=array[1]
    elif i==1:
        dp[2]=array[2]+array[1]
    elif i==2:
        dp[3]=max(array[2]+array[3],array[1]+array[3])


for k in range(4,n+1):
    dp[k]=max(dp[k-2]+array[k],dp[k-3]+array[k-1]+array[k])

print(dp[n])

 

결과