[백준(BOJ)] 9095번 1, 2, 3 더하기

문제

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.

예시

Example 1:

Input: 3
	4
	7
	10
Output: 7
	44
	274

풀이

from collections import deque

def bfs(n):
    q = deque([0])
    count = 0

    while q:
        value = q.popleft()
        # q에 있는 숫자를 n이랑 같거나 커질때까지 1~3을 계속 더해준다
        for i in range(1, 4):
            new_value = value + i
            if new_value <= n:
                if new_value == n:
                    count += 1
                else:
                    q.append(new_value)
    return count

t = int(input())

for _ in range(t):
    n = int(input())
    result = bfs(n)
    print(result)

 

- BFS를 이용하여 1에서 3까지 값을 계속해서 더해가면서 n에 도달하는 경우의 수를 계산하고 출력한다.