백준 9095번 1, 2, 3 더하기 bfs로 한방에 통과!

출력

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

예제 입력 1 복사

3 4 7 10

예제 출력 1 복사

7 44 274

 

 

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


void bfs(int n, int lev)
{
	queue <int> que;
	que.push(lev);
	int now;
	int cnt = 0;
	while (1)
	{
		if (que.empty())
			break;
		now = que.front();
		que.pop();
		if (now == n)
		{
			cnt++;
		}
		if (now + 1 <= n)
			que.push(now + 1);
		if (now + 2 <= n)
			que.push(now + 2);
		if (now + 3 <= n)
			que.push(now + 3);
	}
	cout << cnt <<"\n";
}

int main(void)
{
	int n, a;
	cin >> n;
	for (int i = 0; i < n;i++)
	{
		cin >> a;
		bfs(a, 0);
	}

}

한번에 통과!

그 전전문제랑 똑같이 bfs로 품