BOJ 9095 - 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력#

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이#

마지막에 1을 붙였는지, 2를 붙였는지, 3을 붙였는지로 보면 점화식이 바로 나온다. n을 만드는 방법 수는 결국 n-1, n-2, n-3을 만드는 방법 수의 합이다.

코드에서는 작은 수부터 경우의 수를 미리 채워 두고, 테스트케이스마다 필요한 값만 바로 출력한다. 같은 계산을 반복하지 않는 것이 핵심이다.

직접 조합을 세려 들면 금방 복잡해지지만, 마지막 선택만 생각하면 구조가 아주 단순해진다.

코드#

//진짜 숫자 계산 못하는게 맞는듯
#include <iostream>
using namespace std;
 
int check(int n) {
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	if (n == 3) {
		return 4;
	}
	else {
		return check(n - 1) + check(n - 2) + check(n - 3);
	}
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int T;
	cin >> T;
 
	int n;
	while(T--) {
		cin >> n;
		cout << check(n) << '\n';
	}
 
	return 0;
}

복잡도#

• 시간 복잡도: 필요한 범위까지 DP를 채우므로 $O(N)$이다.
• 공간 복잡도: DP 배열을 저장하므로 $O(N)$이다.

마무리#

마지막에 1, 2, 3을 붙인 세 경우만 이어 보면 1·2·3 더하기 점화식이 완성된다.