백준 9095번 : 1, 2, 3 더하기

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

분석

정수 n이 주어졌을 때 1, 2, 3의 합으로 나타내야 한다. 3은 1, 2로, 2는 1로 표현할 수 있으므로 3이 들어가는 수는 (3), (1+1+1), (1+2), (2+1) 의 총 4가지가 곱해져야 한다. 같은 방향으로 2가 들어가는 수는 (2), (1+1)의 2가지가 들어가야 한다.

방향 때문에 컴비네이션이 필요할 것 같다. 재귀함수까지 쓰면 괜찮을 것 같다.

int  count(int n){
    if(n == 1) return 1;
    if() return ()
    ...

코드

#include <iostream>
using namespace std;

int count(int n) {
	if (n == 0 || n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	return count(n - 1) + count(n - 2) + count(n - 3);
}

int main() {
	int N, elem;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> elem;
		cout << count(elem) << endl;
	}
	return 0;
}

아이고 간만에 한번에 맞췄다. 그래도 꽤 생각하는데 오래 걸렸다.

재귀를 사용하여 분석 때 나온 숫자들을 맞춰주고 return count(n - 1) + count(n - 2) + count(n - 3); 을 통해 3에서 2로, 2에서 1로 변할 수 있는 경우의 수들을 다 더해주었다. 사실 이것만 생각했다면 바로 끝났을 것이다.

다른 블로그들을 찾아보니 0에서 1, 2, 3을 더해가면서 elem이 되는 경우를 count한 곳도 있었다. 그런데 애초에 재귀를 쓰고 싶었기 때문에 다음과 같이 구현하였다.