BOJ-9095 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

문제 소개

주어진 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 이전에 풀이했던 https://www.acmicpc.net/problem/1904와 유사한 문제이다. 이전 단계의 값들로부터 다음 단계의 값이 도출된다.

문제 풀이

• 문제를 처음 푼 방법은 dp가 아닌 조합이었다. 주어진 n을 1, 2, 3의 합으로 나타낼 때 각 숫자가 몇 번씩 쓰일 수 있는지 알아낸 후 조합을 통해 경우의 수를 구하였다.

  이 방법은 직관적이지만, n이 커진다면 연산에 드는 비용이 커질 것이다. 본 문제에서는 n이 11보다 작은 양수였기 때문에 이런 단점이 부각되지 않았다.

• 두번째 방법은 문제 소개에서 언급했던 방식이다.

  n을 1, 2, 3의 합으로 나타내는 방법의 수는 아래와 같다.

  1. n - 1을 1, 2, 3의 합으로 나타내고 끝에 1을 더한다.
  2. n - 2을 1, 2, 3의 합으로 나타내고 끝에 2을 더한다.
  3. n - 3을 1, 2, 3의 합으로 나타내고 끝에 3을 더한다.

  n을 1, 2, 3의 합으로 나타내는 방법의 수를 $f(n)$이라고 하면 $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$과 같은 점화식을 얻을 수 있다.

  초기조건인 n이 각각 1, 2, 3인 경우의 $f(n)$을 초기화해주고 나머지 n에 대한 $f(n)$을 계산한다.

두번째 방법은 첫번째 방법보다 연산 과정이 훨씬 간단하다.

코드

# 첫번째 방법
import sys
from math import factorial as fact
input = lambda: sys.stdin.readline().rstrip()


def comb(n, r):
    return fact(n) // fact(n - r) // fact(r)


t = int(input())
for _ in range(t):
    cnt = 0
    n = int(input())
    for i in range(n // 3 + 1):
        # print(f"3의 개수 : {i}")
        for j in range((n - i * 3) // 2 + 1):
            # print(f"2의 개수 : {j}")
            # print(f"1의 개수 : {n - i * 3 - j * 2}")
            # print(f"숫자의 개수 : {n - i * 2 - j}")
            cnt += comb(n - i * 2 - j, i) * comb(n - i * 3 - j, j)
    print(cnt)

# 두번째 방법
import sys
input = lambda: sys.stdin.readline().rstrip()

arr = [1, 2, 4]
for i in range(3, 10):
    arr.append(arr[i - 1] + arr[i - 2] + arr[i - 3])

t = int(input())
for _ in range(t):
    n = int(input())
    print(arr[n - 1])