링크 : 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한 곳도 있었다. 그런데 애초에 재귀를 쓰고 싶었기 때문에 다음과 같이 구현하였다.