아래로부터의 혁명 (백준 9095 : 1, 2, 3 더하기)

9095번: 1, 2, 3 더하기 (acmicpc.net)

9095번: 1, 2, 3 더하기

 - 대전략 :

 예를 들어 입력값이 5(N)라고 하자. 일단 1부터 올라가야 할 것이다. 그러면 [1 1 1 1 1]이 될 것이고 이 조합의 수는 1개이다. 

그다음은 1 2개를 합쳐서 [2 1 1 1]을 만들고 이 조합의 수는 4! (요소의 갯수) / 3! (중복된 숫자의 갯수) 가 된다. 

리스트 안의 1, 2, 3의 갯수를 리스트화 하자. arr = [a b c]에서, a는 3의 갯수, b는 2의 갯수, c는 1의 갯수가 된다.

즉, [1 1 1 1 1] 은 arr=[0 0 5] 가 되고, [2 2 1]은 arr=[0 2 1], [3 2]는 arr=[1 1 0]이 된다. 

각 abc의 최대 숫자는  N//3, N//2, N//1 이 될 것이다. 

 

 

모든 경우의 수를 도출해야하기 때문에, 재귀함수로 풀어준다. 

 

 

 

라고 말할뻔

 

몇시간동안 고민했는데, 재귀함수로 잘 안풀어진다. 

조건이 너무 많아지나?

그래서 그냥 for문 3번 돌렸다. 사실, 이게 더 간단하게 나온거 같긴하다.

 

import sys
import math

time = int(sys.stdin.readline())



def cal(arr, t):
    cal_num = (math.factorial(sum(arr))) // (math.factorial(arr[2]) * math.factorial(arr[1]) * math.factorial(arr[0]))
    return cal_num



def doing(t):
    res = 0
    for i in range(t//3+1):
        arr[0] = i
        for j in range(t//2+1):
            arr[1] = j
            for k in range(t//1+1):
                arr[2] = k
                if arr[0] * 3 + arr[1] * 2 + arr[2] * 1 == t:

                    res += cal(arr, t)
    print(res)


for i in range(time):
    t = int(sys.stdin.readline())
    arr = [0, 0, t] # 3 갯수, 2 갯수, 1 갯수
    count = 0
    doing(t)

 

너무 억지로 재귀로 풀려했나?

간단하게 풀 수 있으면 간단하게 답인 것 같다.