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

9095번 1,2,3더하기 문제 풀이

문제

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

  • '4' 입력 시 나타낼 수 있는 방법

      1+1+1+1
      1+1+2
      1+2+1
      2+1+1
      2+2
      1+3
      3+1

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

• 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제

입력
3
4
7
10

출력 
7
44
274

해결방법

• 브루트포스가 아닌 DP를 활용하면 쉽게 해결할 수 있으나 이 카테고리에서는 브루트포스로 해결해보려고 한다.

    int plus_1(int sum, int ans) {
    if (sum > ans) return 0;
    if (sum == ans) return 1;
    int hap = 0;
    for (int i = 1; i <= 3; i++) {
        hap += plus_1(sum + i, ans);
    }
    return hap;
    }

  • plus_1이라는 재귀함수를 통하여 더해지는 마지막 인자 값이 1이 될 때 까지 즉 1++1+...+1의 결과 값이 나올 때 까지 반복한다.

  • 이 때 sum값은 i의 값 즉 더해지는 인자 값을 더하여 ans와 비교하여 같을 시 경우의 수가 1이 증가하게 되니 1을 return하여 hap에 더해준다.

      sum = 0 , ans = 3
      for (int i = 1; i <= 3; i++) {
      hap += plus_1(sum + i, ans);
      }
      >>plus_1(1,3)
      >>>plus_1(2,3)
      >>>>plus_1(3,3) - return 1
      >>>>plus_1(4,3) - return 0
      >>>>plus_1(5,3) - return 0
      >>>plus_1(3,3) - return 1
      >>>plus_1(4,3) - return 0
      >>plus_1(2,3) 
      >>>plus_1(3,3) - return 1
      >>>plus_1(4,3) - return 0
      >>>plus_1(5,3) - return 0
      >>plus_1(3,3) - return 1

코드

#include<iostream>
#include<algorithm>
using namespace std;

int plus_1(int sum, int ans) {
    if (sum > ans) return 0;
    if (sum == ans) return 1;
    int hap = 0;
    for (int i = 1; i <= 3; i++) {
        hap += plus_1(sum + i, ans);
    }
    return hap;
}

int main() {
    int t;
    int result;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        result = plus_1(0, n);
        cout << result << '\n';
    }
}