[Baekjoon][C++] 9095번 1, 2, 3 더하기 문제설명 및 코드

▷ 문제설명

9095번: 1, 2, 3 더하기

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

이 때, n의 범위는 1<=n<=10이다.

 

▷ 문제풀이

N이 10보다 작거나 같은 양수이기 때문에 N은 최대 10개 이하의 1,2,3의 수로 표현이 가능하다.

1+1+1+1+1+1+1+1+1+1 = 10

 

1) 10중 for문을 활용하여 한 자리에 하나씩 값을 대입해보면서 n의 값과 같은지를 확인한다.

n의 값과 같다면 해당 경우는 올바른 경우의 수므로 방법의 수를 count한다.

2) 재귀함수를 활용하여 인자로 sum, goal 값을 보내고 돌아올 때(재귀함수 return)마다 count 한다. 

 

▷ 시간복잡도

3가지 경우의 수를 10번 더하면 되므로 O(3*10) = O(1)의 시간복잡도를 갖는다.

 

▷ 정답코드

#include <iostream>
#include <vector>
using namespace std;

void Input();
int PresentSum(int T, int v);

int main() {
	Input();
	return 0;
}

void Input() {
	int T = 0;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int num = 0;
		cin >> num;
		cout << PresentSum(T, num) << endl;
	}
}

int PresentSum(int T, int num) {
	for (int t = 0; t < T; t++) {
		int count = 0;
		for (int l1 = 1; l1 <= 3; l1++) {
			if (l1 == num) {
				count++;
			}
			for (int l2 = 1; l2 <= 3; l2++) {
				if (l1 + l2 == num) {
					count++;
				}
				for (int l3 = 1; l3 <= 3; l3++) {
					if (l1 + l2 + l3 == num) {
						count++;
					}
					for (int l4 = 1; l4 <= 3; l4++) {
						if (l1 + l2 + l3 + l4 == num) {
							count++;
						}
						for (int l5 = 1; l5 <= 3; l5++) {
							if (l1 + l2 + l3 + l4 + l5 == num) {
								count++;
							}
							for (int l6 = 1; l6 <= 3; l6++) {
								if (l1 + l2 + l3 + l4 + l5 + l6 == num) {
									count++;
								}
								for (int l7 = 1; l7 <= 3; l7++) {
									if (l1 + l2 + l3 + l4 + l5 + l6 + l7 == num) {
										count++;
									}
									for (int l8 = 1; l8 <= 3; l8++) {
										if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 == num) {
											count++;
										}
										for (int l9 = 1; l9 <= 3; l9++) {
											if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 == num) {
												count++;
											}
											for (int l10 = 1; l10 <= 3; l10++) {
												if (l1 + l2 + l3 + l4 + l5 + l6 + l7 + l8 + l9 + l10 == num) {
													count++;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return count;
	}
}

#include <iostream>
using namespace std;

int PresentSum(int sum, int goal);

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cout << go(0, n) << '\n';
	}
	return 0;
}

int PresentSum(int sum, int goal) {
	if (sum > goal) {
		return 0;
	}
	if (sum == goal) {
		return 1;
	}
	int count = 0;
	for (int i = 1; i <= 3; i++) {
		count += go(sum + i, goal);
	}
	return now;
}