[백준] 9095번 - 1, 2, 3 더하기 | 파이썬

SangJin Ham·2023년 7월 7일

BFS DP 백준 알고리즘

백준

목록 보기

31/51

9095번 - 1, 2, 3 더하기

시간제한 : 1초(추가 시간 없음)
메모리 제한 : 512MB

문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

예제 출력 1

7
44
274

BFS 코드

import sys
from collections import deque

T = int(sys.stdin.readline().strip())

for _ in range(T):
    n = int(sys.stdin.readline().strip())
    
    Q = deque([1, 2, 3])
    cnt = 0
    while Q:
        length = len(Q)
        for _ in range(length):
            v = Q.popleft()
            if v == n:
                cnt += 1
                continue
            for nv in [1, 2, 3]:
                tmp = v + nv
                if tmp <= n:
                    Q.append(tmp)
    print(cnt)

BFS 풀이

시간 : 68ms
메모리 : 34104KB

먼저 나는 BFS가 먼저 떠올라서 BFS로 풀어봤다.
Q에 1, 2, 3을 넣고 하나씩 꺼내서 자식 노드를 만드는데 예를 들면 첫 번째 노드인 1을 꺼내면 1+1, 1+2, 1+3로 자식 노드를 만드는데 이때 1~3을 더했을 때 n보다 크다면 Q에 삽입하지 않는 것으로 제한을 뒀다.
그리고 꺼낼 때마다 만약 n과 동일하다면 cnt + 1한 후 경우의 수를 다 세고 n을 완성시킬 수 있는 cnt를 출력해줬다.

DP 코드

import sys

def dp(n):
	if n == 1:
    	return 1
    elif n == 2:
    	return 2
    elif n == 3:
    	return 4
    else:
    	return dp(n-1) + dp(n-2) + dp(n-3)


T = int(sys.stdin.readline().strip())

for _ in range(T):
    n = int(sys.stdin.readline().strip())
	print(dp(n))

DP 풀이

시간 : 40ms
메모리 : 31256KB

BFS로 풀어보고 다른 사람들은 어떻게 풀었나 찾아보았더니 대부분 DP(동적계획법)로 풀어냈다.

먼저 이 문제의 1~3의 합으로 만들 수 있는 경우의 수는 아래와 같다.

n	경우의 수	개수
1	(1)	1
2	(1+1), (2)	2
3	(1+1+1), (1+2), (2+1), (3)	4
4	(1+1+1+1), (1+1+2), (1+2+1), (1+3), (2+1+1), (2+2), (3+1)	7
5	(1+1+1+1+1), (1+1+1+2), (1+1+2+1), (1+1+3), (1+2+1+1), (1+2+2), (1+3+1), (2+1+1+1), (2+1+2), (2+2+1), (2+3), (3+1+1), (3+2)	13