[백준] 2579번 계단오르기

 

사실 이 문제를 계기로 DP를 먼저 공부하기로 마음 먹었던 것입니다.

풀다가 6개 실패했습니다..알고보니 DP 알고리즘으로 푸는 문제였습니다. ㅎㅎ

그래서 지난 포스팅에서 DP를 푸는 이론을 먼저 공부하고 다시 도전하게 되었습니다.

 

접근법

- DP

- 최댓값을 가지게 하는 방법

- 1,2번 계산을 무조건 밟는다

- 3번 계산부터 마지막 계산까지는 1칸 or 2칸을 이동

- i 번째 칸 일때 가능한 경우는 1) i-2칸에서 오는 경우와 2) i-3칸에서 i-1로 이동하여 오는 경우

*3칸을 연속해서 이동하지 못하는 점 고려

 

n = int(input())
scores = [0]
scores += [int(input()) for _ in range(n)]
dp = [0 for _ in range(n+1)]

def func_dp(n):
    if n == 1 :
        return scores[1]
    
    dp[1] = scores[1]
    dp[2] = scores[1] + scores[2]
    
    for i in range(3,n+1):
        dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i])
        
    return dp[n]

print(func_dp(n))

 

 

동적 계획법 해결 : 소문제로 쪼개어 해결

- 최대값을 구하기 위한 규칙성을 가지는 작은 문제로 나누어 해결했습니다.

        dp[i] = max(dp[i-2]+scores[i], dp[i-3]+scores[i-1]+scores[i])

 

 

아직 작은 문제로 쪼개서 생각하는 문제를 더 풀어볼 필요가 있을 것 같습니다.

DP 관련 문제를 더 풀어볼 계획입니다.