[Python][백준] 9095번 문제 1, 2, 3 더하기 해결 | DP는 어려워

동적 계획법(dynamic programming, DP)

DP 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.

DP의 핵심 작은 부분을 기억하는 것이다.

왜냐하면 Optimal Structure가 있는 문제를 풀 때 구조를 새로 구할 필요없이, 방금 전 기억한 작은 부분을 불러오면 더 빠르고, 효율적으로 구할 수 있기 때문이다.

 

오늘은 DP를 이용하여 푼 1, 2, 3 더하기 문제를 풀어보겠다.

lines = int(input())
cases = list(int(input()) for _ in range(lines))
for c in cases:
    dp = [0, 1, 2, 4] + [0 for _ in range(c)]
    for i in range(4, c+1):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[c])

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이 문제의 합의로 나타내는 방법은 순서가 있다. 

정수 1, 2, 3은 숫자 1, 2, 3 중 하나만으로도 표현할 수 있으니 논외로 하자.

 

정수 4를 숫자 1, 2, 3의 합으로 나타내려면, 1, 2, 3 중 최소 2개 이상 사용하여야한다.

 

즉 정수 4의 경우의 수는

(정수 1의 합 + 정수 3의 합)

(정수 2의 합 + 정수 2의 합)

(정수 3의 합 + 정수 1의 합)

으로 나타낼 수 있다.

 

중복되는 경우를 제외하면, 정수 4의 합을 나타낼 수 있는 경우는

((정수 1의 합 + 정수 3의 합) + (정수 2의 합 + 정수 2의 합) + (정수 3의 합 + 정수 1의 합)) / 2

즉 정수 1의 합 + 정수 2의 합 + 정수 3의 합으로 나타낼 수 있고,

 

이것은

dp[4] = dp[1] + dp[2] + dp[3]

으로 코드를 쓸 수 있고

이것은

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

으로 일반화할 수 있다.