[백준/C++] 9095번 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

문제 분석

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라.

조건. n은 양수 이며 11보다 작다.

코드

#include <iostream>

using namespace std;

int n;
int cnt;

void caseNum(int num){
	if(num==0){
		cnt++;
		return;
	}
	for(int i=1; i<=3; i++){
		if(num-i>=0){
			caseNum(num-i);
		}
	}
}

int main(){
	cin>>n;
	int input[n];
	for(int i=0; i<n; i++) {
		cin>>input[i];
	}
	for(int i=0; i<n; i++) {
		cnt = 0;
		caseNum(input[i]);
		cout<<cnt<<"\n";
	}
	return 0;
}

문제 풀이

1. 테스트 케이스의 개수 n과 테스트 케이스 n개를 배열 input으로 입력받는다.

2. input의 값을 인자로 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 caseNum 함수를 실행한다.

3. 1, 2, 3의 합으로 나타내야 하므로 i의 범위를 1부터 3이하로 설정하여 반복문을 실행한다.

4.  1, 2, 3의 합이 테스트 케이스보다 크면 안 되므로 num-i가 0 이상일 때만(0보다 작으면 1, 2, 3의 합이 테스트 케이스보다 크다는 뜻이기 때문)  num-i(테스트 케이스에서 1 또는 2 또는 3을 뺀 값)를 인자로 caseNum함수를 호출한다.

5. 이처럼 caseNum 함수를 재귀적으로 실행하다가 num이 0이 되면, 즉 경우(1, 2, 3의 합이 테스트 케이스와 일치할 때)가 완성되었다면, 경우의 수인 cnt를 1 증가시키고 함수를 종료한다.

6. 이후 반복문이 돌면서 계속해서 다음 경우를 완성시킬 때마다 cnt가 증가한다. 

(실행 예: 테스트 케이스: 3

1. caseNum(3) 호출, i=1: caseNum(2) 호출
2. caseNum(2)에서 i=1: caseNum(1) 호출
3. caseNum(1)에서 i=1: caseNum(0) 호출
4. caseNum(0)에서 num이 0이므로 경우 완성(1+1+1), cnt 증가, caseNum(0) 종료
5. caseNum(1)에서 i=2: num-i가 -1이므로 caseNum(1) 종료
6. caseNum(2)에서 i=2: caseNum(0) 호출
7. caseNum(0)에서 num이 0이므로 경우 완성(1+2), cnt 증가, caseNum(0) 종료
8. caseNum(2)에서 i=3: num-i가 -1이므로 caseNum(2) 종료
9. caseNum(3)에서 i=2: caseNum(1) 호출 (이후 위와 비슷한 과정 반복)

)

7. cnt는 caseNum 함수 실행 전마다 0으로 초기화해줘야 각 테스트 케이스에 맞는 경우의 수를 구할 수 있다.