[9095] 1,2,3 더하기

문제 : 1,2,3 더하기

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1
  정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

문제 정리

• 다른 수식이 있지 않고 오로지 더하기만을 사용한 문제이다. 때문에 다른 비슷한 유형과 비교했을 때, 좀 더 쉽다.
• 재귀와 dp를 적절히 사용해서 문제를 풀면 된다.
• 일단 규칙을 찾기 위해서 각 숫자별로 몇 개의 합의 개수가 있는지 brute하게 탐색해보도록 하자.

숫자가 1~10까지만 존재한다. 때문에 N이 되는 숫자의 조합을 찾는 것은 모든 경우의 수를 다 찾아서 출력하더라도 문제가 안된다.

풀이

1. 첫 풀이

    # 재귀를 통해 모든 입력받은 num에 대해 1,2,3 더하기를 통해 만들어지는 모든 경우의 수를 반환
	def find_combination(current, num):
        if current == num: # 특정 조합의 덧셈이 num과 같다면 count +1
            return 1
        if current > num: # 아니라면 0
            return 0
        cnt = 0
        for i in range(1,4): # 1,2,3에 대해 모든 조합의 수를 재귀로 구함.
            cnt += find_combination(current+i, num)
	    return cnt

    t = int(input()) # 테스트 케이스 수
    for _ in range(t):
        i = int(input()) # 조합을 찾아야 하는 수
        print(ind_combination(0, i))

첫 번째 풀이는 재귀를 통해 모든 조합의 수를 구하는 것이 목적이다.
1~3까지 모든 경우의 수에 대해 더해가며 입력받은 숫자가 나온다면 count에 1을 더하며 재귀로 반복한다.
이 방법은 숫자가 커질수록 시간복잡도 면에서 통과하지 못할 것이다.
때문에 보통 이러한 문제들은 점화식을 통해 접근해야한다.

2. 두번째 풀이

일단 첫번째 풀이를 통해 모든 경우의 수를 구해보았다.
[1, 2, 4, 7, 13, 24, 44, 81, 149, 274] 가 나오는 것을 확인 가능했다.
여기서 규칙을 찾아보자면 ,
n>=4라면
T[n] = T[n-1] + T[n-2] + T[n-3]이라는 것을 알 수 있다.
해당 수식을 코드로 표현해보자.

 sum_combinaiton = [1,2,4] # n<4인 값들을 미리 저장
 for i in range(3, 11): # 나머지 n>=4부터 10까지의 경우의 수를 미리 저장
 	# T[n] = T[n-1] + T[n-2] + T[n-3]
     n_sum = sum_combinaiton[i-1] + sum_combinaiton[i-2] + sum_combinaiton[i-3]
     sum_combinaiton.append(n_sum)

 t = int(input())
 for _ in range(t):
     i = int(input())
     print(sum_combinaiton[i-1])
	```