[DP] 9095, 15988번 1,2,3 더하기

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

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

알고리즘

• Brute Force
• Dynamic Programming

풀이

포인트

• 같은 숫자를 여러번, 연속적으로 사용해도 된다는 점
• 정수 n을 구성하는 숫자의 순서는 상관 없다는 점
  • 1+1+2, 1+2+1, 2+1+1은 모두 다른 경우의 수
• 정수 n을 구성하는 숫자의 개수의 제한이 없다는 점

Brute Force

문제에서 n은 11보다 작다. 따라서 n은 최대 10개의 수로 구성될 수 있다. 그러면 각 자리마다 가능한 정수 (1,2,3)를 모두 놓아봄으로써 가능한 경우 (그 정수들의 합이 n)만 체크해주면 된다.

Brute Force로 프로그래밍할 때, 재귀를 이용하는 것을 즐겨하기 때문에 재귀를 이용하여 모든 경우를 탐색해주었다. 일 때는 문제의 조건에 충족하는 경우니까 ans에 1을 더해주고 일 때는 조건에 맞지 않는 경우이니 그냥 넘어가준다.

각 자리수마다 3개의 수를 탐색한다. 즉, 각 자리수에 1,2,3을 for문에서 재귀적으로 넣어보는 것인데 따라서 go 함수가 끝나면 더해줬던 수인 numbers[i]를 다시 빼준다. 이러한 재귀적인 과정 때문에 시간 복잡도는 이다. 최대 10자리이고 각 자리마다 세 개의 수인 1,2,3을 넣을 수 있기 때문이다.

[Source Code]

t = int(input())
def go(s, n):
  global ans
  if s == n:
      ans += 1
      return
  if s > n:
      return
  for i in range(3):
      s += numbers[i]
      go(s, n)
      s -= numbers[i]
for _ in range(t):
  n = int(input())
  numbers = [1,2,3]
  ans = 0
  go(0,n)
  print(ans)

Dynamic Programming

앞서 살펴본 Brute Force 풀이는 $n < 11$이기에 가능한 풀이이다. 즉, $n$이 조금만 더 커져도 시간초과가 뜰게 뻔하다. 15988번을 위의 Brute Force로 푼다면 복잡도는 $O(3^{1000000})$으로, 시간초과가 뜬다.

복잡도를 줄이기 위해, DP를 이용한다. 먼저, dp 테이블과 점화식을 아래와 같이 정의한다.

• $dp[i]$ : 정수 $i$를 1,2,3을 이용하여 만드는 경우의 수
• $dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$

정수 $i$에서 1만큼 떨어진 정수인 $i-1$에서 $i$을 만들기 위해서는 1을 더해주면 되고, 2만큼 떨어진 정수인 $i-2$에서 $i$를 만들기 위해서는 2를, 3만큼 떨어진 정수인 $i-3$에서 $i$을 만들기 위해서는 3을 더해주면 된다. 각 수를 더해주는 것은 $i-j$를 만드는 경우의 수를 그대로 가져오고 $j$만 더해주는 것이다. 따라서 위의 점화식을 세울 수 있다.

DP 테이블이 $n \times 1$의 1차원이므로, 시간 복잡도는 $O(n)$이다. 따라서 $n = 1000000$ 이더라도 파이썬으로 1초 이내에 문제를 해결할 수 있다.

[Source Code]

m = 1000000
dp = [0]*(m+1)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4,m+1):
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000009

n = int(input())
for _ in range(n):
    a = int(input())
    print(dp[a])