백준 #15989 - [S1] 1,2,3 더하기 4 : DP

(python3)

15989번: 1, 2, 3 더하기 4

 

수학으로 해결하기

1,2,3으로 조합해서 수를 만드는 방법은, 3을 먼저 넣고, 남은 값을 2로 만들고, 그리고 남은 값은 1을 채우는 것과 같다.

코드

import sys

def solution(input) :
    N = int(input().strip())
    for _ in range(N) :
        S = 0
        n = int(input().strip())
        for i in range(n//3 + 1) : # 3으로 채울 수 있는 모든 경우의 수
            S += (n - i*3)//2 + 1 # 남은 수에서 2로 채울 수 있는 모든 경우의 수
        print(S)
        
input = sys.stdin.readline
solution(input)

 

DP 활용

0~10000까지 모든 값을 DP로 미리 계산한다.

일단 모든 수는 1만으로 만들 수 있으므로 1을 다 채운다.

여기에 2를 추가로 사용하는 방법은 (기존 x를 만드는 방법 수) + (x-2를 만드는 방법들에 2 하나를 추가)

즉 dp 테이블 상에서는 dp[x] += dp[x-2]

코드

import sys
def solution(input) :
    N = int(input().strip())
    dp = [1]*10001

    for i in range(2,10001) :
        dp[i] += dp[i-2] # 1에 2를 섞어서 만들 수 있는 경우
    for i in range(3,10001) :
        dp[i] += dp[i-3] # 거기에 3을 섞어서 만들 수 있는 경우

    for _ in range(N) : # DP로 미리 연산한걸 출력
        n = int(input().strip())
        print(dp[n])

        
input = sys.stdin.readline
solution(input)

 

DP가 참 유용한데 떠올리기가 쉽지 않네요ㅜㅜ

my solved.ac :

solved.ac