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

1. 문제이해

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

9095번: 1, 2, 3 더하기

 

정수가 주어졌을 때, 해당 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

정수 N이 주어지고, 해당 정수를 1, 2, 3으로 나타낼 수 있는 경우의 수를 출력해야한다.

주의해야 할 점은 숫자를 반드시 1, 2, 3 의 합으로만 나타내야 한다는 것이다.

또한, 위의 정수 4에 대한 예제 풀이로 보았을 때,

순서를 바꿔 더하는 경우도 다른 경우로 포함시켜야 함을 알 수 있다.

(위의 예제에서 1+1+2, 1+2+1을 다른 경우로 세어준 경우)

 

따라서, 이에 유의해서, 1부터 5까지의 숫자를 1, 2, 3의 합으로 나타내어 보면

다음과 같은 결과를 얻을 수 있다.

 

 

위 그림을 보면, 4부터 일정한 규칙에 따라 1, 2, 3의 합으로 나타내어지는 것을 확인할 수 있다.

 

4의 경우에는,

결괏값은

3(4-1)의 경우의 수들 + 1

2(4-2)의 경우의 수들 + 2

1(4-3)의 경우의 수들 +3

개수는

3(4-1)의 경우의 수들  + 2(4-2)의 경우의 수들  + 1(4-3)의 경우의 수들

이 나왔다.

 

또 다른 경우인 5의 경우에는,

결괏값은

4(5-1)의 경우의 수들 + 1

3(5-2)의 경우의 수들 + 2

2(5-3)의 경우의 수들 +3

개수는

4(5-1)의 경우의 수들  + 3(5-2)의 경우의 수들  + 2(5-3)의 경우의 수들

이 나왔다.

(1의 경우의 수들의 경우에는 1+4로, 1, 2, 3의 합이 아니기 때문에 제외)

 

따라서, 정수 N을 1, 2, 3의 합으로 나타낼 수 있는 가짓수는

(N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수 가 된다.

(우리가 구하는 것은 결과값이 아니라 경우의 수의 개수이다!)

이를 재귀를 통해 아래와 같은 코드로 구현해보았다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int add(int n) {
	if (n == 1) {	// 정수가 1인 경우
		return 1;
	}

	else if (n == 2) {	// 정수가 2인 경우
		return 2;
	}

	else if (n == 3) {	// 정수가 3인 경우
		return 4;
	}

	// 정수 N을 1, 2, 3 의 합으로 나타낼 수 있는 경우의 수는
	// (N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수
	return add(n - 1) + add(n - 2) + add(n - 3);
}

int main() {
	int T; // 테스트 케이스의 개수
	int arr[10000];	// 각 테스트 케이스의 정수
	int result[10000]; // 1, 2, 3의 합으로 나타낼 수 있는 경우의 수 

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> arr[i];	// 정수를 입력받아
		result[i] = add(arr[i]); // 경우의 수를 계산하여 result 배열에 넣기
	}

	for (int i = 0; i < T; i++) {
		cout << result[i] << '\n';
	}

	return 0;
}

함수를 따로 구현하여 2. 문제풀이의 방식대로 코드를 구현했다.

테스트 케이스의 개수(T)와 각 정수들(arr[i])을 입력받아, add 함수를 통해 경우의 수를 계산하고,

계산한 값을 result[i] 배열에 넣어 이를 다시 출력해주었다.

 

add 함수의 경우에는,

들어온 정수가 1, 2, 3인 경우에는 바로 해당 경우의 수를 반환하고,

아닌 경우에는 (N-1)의 경우의 수 + (N-2)의 경우의 수 + (N-3)의 경우의 수를 구해

반환하도록 구현했다.

 

 

---

역시 무슨 문제이던지 간에 써보고 푸는게 제일인 것 같다..

한참 들여다보고 풀려고 할때는 안풀리더니,

노트에 이래저래 써보고 하니 금방 규칙을 찾을 수 있었던 문제였다.

혹여나 궁금한 점이나 이해가 안되는 점이 있다면 언제든지 댓글은 환영입니다.🤗