[백준2579번][백준][baekjoon][2579번][DynamicProgramming][DP][계단오르기][Python][파이썬]

문제링크

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

2579번: 계단 오르기

 

문제

 

풀이

가장 전형적인 DP문제가 아닌가 생각됩니다. 각 계단에 도달할 때의 점수를 DP에 저장하는 방식으로 풀면 될 것 같습니다. 이 문제는 3가지 조건을 가지고 있습니다. 

 

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

3번 조건 "마지막 계단을 반드시 밟아야 한다." 라는 조건을 빠드리지 않도록 주의해야 합니다. 이 조건을 생각하면서 마지막 계단을 밟고, 위 세 가지 조건을 모두 만족하고 최대한 점수를 많이 회득하는 경우는 다음과 같습니다. 설명의 편의상 마지막 계단의 번호를 N이라고 하겠습니다.

 

1. N-2 번째 계단은 밟지 않고, N-1 번째 계단을 밟는경우. 

2. N-2 번째 계단을 밟고, N-1번째 계단을 밟지 않는 경우. 

 

위 두가지 경우는 N번째 계단을 밟을 수 있는 조건과 동시에 위 세 가지 조건을 모두 만족하는 경우입니다. 두 경우 중에서 더 높은 점수를 회득하는 경우가 N번째 계단을 밟으면서 점수를 최대한 회득하는 경우가 되겠습니다. 이를 점화식으로 나타내면 아래와 같습니다. 각 계단에서 회득하는 점수는 steps로 나타내겠습니다.

 

if D[N-2] > D[N-3] + steps[N-1]  :  D[N]=D[N-2]+steps[N]

else: D[N]  =  D[N-3]+steps[N-1]+steps[N]

 

코드

#python

 

testcase=int(input())
 
dp=[ 0 for _ in range(302) ]
steps=[0 for _ in range(302) ]
for i in range(1,testcase+1):
    score=int(input())
    steps[i]=score
    if i==1:
        dp[i]=score
    elif i==2:
        dp[i]=dp[i-1]+score
    else:
        if score+dp[i-2] > dp[i-3]+steps[i-1]+score:
            dp[i]=score+dp[i-2]
        else:
            dp[i]=score+steps[i-1]+dp[i-3]

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.