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

문제 링크

9095번: 1, 2, 3 더하기

 

이 문제는 두 가지 방법으로 풀어봤다.

풀이 1 ) 완전 탐색

  a1, a2, a3에 각각 1, 2, 3의 개수를 저장한 후 그 3가지의 순서 개수를 구했다. 팩토리얼을 구하는 라이브러리 함수가 없으므로 내가 만들었다. 물론 여기서 팩토리얼을 구할 때 재귀 호출이 아닌 dp를 사용하여 구할 수도 있지만 문제에서 주어진 n의 크기가 작으므로 재귀 호출로 구해주었다.

  단 이 때는 팩토리얼의 크기가 int범위를 벗어나지 않는지 확인해줄 필요가 있다. 12! 까지 int로 표현 가능하고 13! 부터는 long long형을 사용하면 되는데 그냥 long long형을 사용하는 게 더 편한 것 같다.

 

#include <cstdio>
using namespace std;

int fac(int);

int main(void)
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        int ans = 0;
        scanf("%d", &n);

        int a1, a2, a3;
        for(a3 = 0; a3*3 <= n; a3++){
            for(a2 = 0; a3*3 + a2*2 <= n; a2++){
                a1 = n - a3*3- a2*2;
                ans += fac(a1+a2+a3)/fac(a1)/fac(a2)/fac(a3);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

int fac(int n)
{
    if(n < 2) return 1;
    else return n*fac(n-1);
}

 

풀이 2 ) dp

  n을 1, 2, 3으로 나타내는 방법은 다시 보면 1로 시작하는 경우와 2로 시작하는 경우와 3으로 시작하는 경우 3가지로 나눌 수 있다. 1로 시작하는 경우는 1과 n-1로 나누고 2, 3도 같은 방식으로 나눌 수 있다. 즉  n을 1, 2, 3으로 나타내는 방법의 수를 f(n)이라 했을 때 f(n) = f(n-1) + f(n-2) + f(n-3)으로 나타낼 수 있다.

  위의 식을 재귀로 구할 수도 있지만 dp를 사용하여 구했다.

 

#include <cstdio>
using namespace std;

int memo[12] = {1, 2, 4, };

int main(void)
{
  int t;
  scanf("%d", &t);
  while(t--){
    int n;
    scanf("%d", &n);
    for(int i = 3; i < n; ++i)
      memo[i] = memo[i-1] + memo[i-2] + memo[i-3];
    printf("%d\n", memo[n-1]);
  }
  return 0;
}