9095번 백준(Baekjoon)

<문제>

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

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

<정답 코드>

#include <iostream>
#include <queue>
 
using namespace std;
 
int n, t;
queue<int> q;
int cnt = 0;
 
void bfs()
{
    q.push(n);
    cnt = 0;
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; i++)
        {
            int front = q.front();
            q.pop();
            if (front == 0) {
                cnt++;
                break;
            }
            if (front - 1 >= 0)
                q.push(front - 1);
            if (front - 2 >= 0)
                q.push(front - 2);
            if (front - 3 >= 0)
                q.push(front - 3);
        }
    }
    cout << cnt << endl;
    return;
}
 
int main()
{
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        bfs();
    }
    return 0;
}