[백준] 15989 1,2,3 더하기 4

문제 설명

문제 링크

1과 2와 3만을 사용해서 더할 때, 특정 수 n을 만드는 경우의 수가 몇 개 있는 지 푸는 문제이다.

오직 1, 2, 그리고 3을 사용하는 횟수에 따라 경우의 수가 결정되며, 순서만 다른 경우는 같은 경우의 수로 친다.

예로, 4를 1, 2, 3의 합으로 만들기 위해서는 다음 네가지 경우의 수가 있다고 한다:

• 1 + 1 + 1 + 1
• 2 + 1 + 1 (= 1 + 2 + 1, 1 + 1 + 2)
• 2 + 2
• 3 + 1 (= 1 + 3)

문제 풀이

이런 류의 문제는 동적 계획법을 사용해서 풀 수 있다.
동적 계획법을 사용할 때는 메모이제이션(재귀)를 사용하든, 타뷸레이션(반복문)을 사용하든 점화식을 세우는 것이 가장 중요하기 때문에 이를 세우려고 했다.

매 번 느끼는 거지만 DP문제는 일정 부분 손으로 직접 그려가면서 눈으로 보는 것이 가장 빠르고 명확하다고 생각한다.

이렇게 dp 테이블과 각 경우의 수 자체를 그려보니까 명확해졌다. 바로 1과 2만을 사용하여 n을 만든 경우의 수에 n-3을 만드는 경우의 수를 더하면 된다. 생뚱맞게 n-3이 어디서 나왔냐면, 사진의 7을 만드는 그림의 네모친 부분을 보면 된다. 3을 사용하기 때문에 첫 수는 3으로 고정했을 때 사실상 1, 2, 3을 사용하여 4를만드는 경우의 수가 1과 2를 사용하여 7을 만드는 경우의 수에 더해지기 때문이다.

물론, 무조건 테이블 전체가 n-3이 아니고, 1과 2만을 사용한 부분을 구하고 싶으면 같은 논리로 n-2를 적용하면 된다.
그러면, 수를 만들기 위해 사용한 최대값을 largest라고 부르면 2차원 배열을 사용했을 때의 점화식은 dp[n, largest] = dp[n-3, largest] + dp[n, largest-1]일 것이다.

다만, 나는 일차원 배열로도 할 수 있지 않을까 싶었다. 문제에서 사용하는 수가 바뀌는 것이 아니라 무조건 1, 2, 3만을 사용하기도 했고, 그린 표를 보면 2행은 꽤나 규칙적으로 커지고 있기 때문에 여기서도 규칙을 찾아서 3행, 즉 문제에서 요구하는 정답이 있을 행만 사용하여 dp테이블을 만들 수 있을 것이라 생각했다.

어차피 n의 범위는 1-10000이기 때문에 0번째 인덱스를 전혀 신경쓰지 않아도 되기에, 0을 1이라고 가정하면 2행은 1, 1, 2, 2, 3, 3과 같이 규칙적으로 상승한다. 여기에서 2행의 식 n//2 + 1을 세울 수 있다.

최종적으로 dp[n] = dp[n-3] + (n//2 + 1)을 세울 수 있다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def dp(num, arr):
    if cache[num] != 0:
        return cache[num]

    if num == 1 or num ==2 or num == 3:
        return num
    
    cache[num] = dp(num-3, cache) + (num//2 + 1)
    return cache[num]
    

if __name__ == "__main__":
    T = int(input())
    
    for _ in range(T):
        n = int(input())
        cache = [0]*10001

        print(dp(n, cache))