[백준] 9095번: 1, 2, 3 더하기

소요 시간 :  95 M

문제 이해하기

하나의 정수 N이 주어질 때, 이 N을 1, 2, 3의 합으로 나타낼 수 있는 순열의 수를 구하라.

예를 들어, N = 4 인 경우, 총 7가지로 나타낼 수 있다.

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

문제 풀이

N이 4인 경우를 생각해 봤을 때, 나올 수 있는 경우는 7가지였다.

이를 리스트로 나타내면 [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2,2]이다.

항상 N을 1만을 사용하여 나타낼 수 있는 경우는 1가지이다. 

2를 한번 사용하고 나머지를 1로 나타낼 수 있는 경우는 N가지이다.

갑자기!

깊이 우선 탐색으로 풀면 좋은 것 같다.

첫 요소로 1을 선택하는 경우, 두 번째 요소로 1과 2와 3을 선택하고, 요소들의 합이 4가 되지 않았다면,

계속해서 다른 요소들을 탐색하는 방식을 사용하면 될 것 같다.

일단 N이 1이거나 2이거나 3인 경우에는

• f(0) = 1
• N = 1,, f(1) = 1
• N = 2,, f(2) = 2 = 1 + 1 = f(1) + f(0)
  • 1 1
  • 2

 

• N = 3,, f(3) = 4 = f(2) + f(1) + f(0)
  • 1 1 1
  • 1 2
  • 2 1
  • 3

 

• N = 4,, f(4) = 7 = 4 + 2 + 1 = f(3) + f(2) + f(1)
  • 1 1 1 1
  • 1 1 2
  • 1 2 1
  • 1 3
  • 2 1 1
  • 2 2
  • 3 1

 

• N = 5,, f(5) = 13 = 7 + 4 + 2 = f(4) + f(3) + f(2)
  • 1 1 1 1 1
  • 1 1 1 2
  • 1 1 2 1
  • 1 1 3
  • 1 2 1 1
  • 1 2 2
  • 1 3 1
  • 2 1 1 1
  • 2 1 2
  • 2 2 1
  • 2 3
  • 3 1 1
  • 3 2

 

• N = 6,, f(6) = 24 = 13 + 7 + 4
  • 내 예상이 맞다면 8 + 6 + 4 = 18이 나올 것이다. → 틀림
  • 1 1 1 1 1 1
  • 1 1 1 1 2
  • 1 1 1 2 1
  • 1 1 1 3
  • 1 1 2 1 1
  • 1 1 2 2
  • 1 1 3 1
  • 1 2 1 1 1
  • 1 2 1 2
  • 1 2 2 1
  • 1 2 3
  • 1 3 1 1
  • 1 3 2
  • 2 1 1 1 1
  • 2 1 1 2
  • 2 1 2 1
  • 2 1 3
  • 2 2 1 1
  • 2 2 2
  • 2 3 1
  • 3 1 1 1
  • 3 1 2
  • 3 2 1
  • 3 3

이거 혹시 규칙성이 있나?

있다!!! f(N) = f(N - 1) + f(N - 2) + f(N - 3)

왜 그럴까?

f(N)은

f(N - 1)의 모든 경우에서 1을 더한 경우를 더하고

f(N - 2)의 모든 경우에서 2를 더한 경우를 더하고

f(N - 3)의 모든 경우에서 3을 더한 경우를 더하는 것이다.

1, 2, 3만을 사용하여 표현하기 때문에

f(N- 4)의 모든 경우에서 4를 더하는 것과 같은 경우는 포함하지 않는다.

규칙성을 찾았으니 코드를 작성해 보아야겠다.

import sys

class Solution():
    def backtrack(self):
        input = sys.stdin.readline
        T = int(input())

        cases = [int(input()) for _ in range(T)]
        res = []

        def dfs(n):
            if n == 0 or n == 1:
                return 1
            elif n == 2:
                return 2

            return dfs(n-1) + dfs(n-2) + dfs(n-3)

        for case in cases:
            total = dfs(case)
            res.append(total)

        for ans in res:
            print(ans)

a = Solution()
a.backtrack()

 

배운 점

너무 오래 걸렸다..

문제들에 익숙해져야 할 것 같다..