[Programmers][Python] Lv.2 멀리 뛰기

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: Lv.2
• 문제 유형: DP
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

[BOJ] 9095 1, 2, 3 더하기

문제와 유사한 문제이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

 

[코드]

def solution(n):
    dp =[0] * 2001
    dp[0] = 1

    for i in range(1, n+1):
        for j in range(1, 3):
            if i >= j:
                dp[i] += dp[i-j]

    return dp[n]%1234567

 

 

[동작 원리]

dp[0] = 1  # 기본값 설정

# i=1일 때 (1을 만드는 방법)
i=1:
    j=1: dp[1] += dp[0] # dp[1] = 1
    j=2: # i(1) < j(2)이므로 실행 안 됨
# dp[1] = 1 (방법: 1)

# i=2일 때 (2를 만드는 방법)
i=2:
    j=1: dp[2] += dp[1] # dp[2] = 1
    j=2: dp[2] += dp[0] # dp[2] = 2
# dp[2] = 2 (방법: 1+1, 2)

# i=3일 때 (3을 만드는 방법)
i=3:
    j=1: dp[3] += dp[2] # dp[3] = 2
    j=2: dp[3] += dp[1] # dp[3] = 3
# dp[3] = 3 (방법: 1+1+1, 1+2, 2+1)

# i=4일 때 (4를 만드는 방법)
i=4:
    j=1: dp[4] += dp[3] # dp[4] = 3
    j=2: dp[4] += dp[2] # dp[4] = 5
# dp[4] = 5 (방법: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

 

dp[i] 에는 만드는 방법의 개수를 저장해준다.