[Algorithm] BaekJoon : 9095. 1, 2, 3 더하기 by Python

[문제 바로가기] https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

📌 문제 설명

정수 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의 합으로 나타내는 방법의 수를 출력한다.

---

💡 문제 풀이

큐(Queue) 자료구조를 이용하여 간단하게 풀었다.

같은 숫자의 개수를 사용하더라도 다른 방법으로 카운팅해야하는 것이 핵심이다.
ex) 1+1+2와 1+2+1은 결과는 같지만 다른 방법으로 카운팅한다.

 

step 1)
deque 라이브러리를 이용하여 queue를 만든다.

이 때, 1, 2, 3 숫자를 이용해서 n을 만들어야 하기 때문에 queue 안에는 [1], [2], [3] 원소를 넣는다.

배열로 넣은 이유는 '순서'를 고려하기 위함이다. 앞서 언급하였듯이 1+2와 2+1은 서로 다른 방법이다.
따라서, [1, 2], [2, 1]처럼 사용한 숫자들을 배열을 이용하여 표현하면 구분할 수 있다.

 

step 2)
queue의 원소가 존재할 때 까지 아래의 과정을 진행한다.

1. queue의 원소를 꺼내 합이 n과 일치하는지 확인한다. → n이 3 이하인 경우 기존 queue의 원소들과 동일한 경우가 생기기 때문
2. 1, 2, 3 숫자를 순차적으로 더하면서 다음의 조건문으로 결과를 판별한다.
   2-1. queue에서 빼낸 원소와 1, 2, 3 숫자를 더했을 때 n과 같다면 answer+1 해준다
   2-2. queue에서 빼낸 원소와 1, 2, 3 숫자를 더했을 때 n보다 크면 break해준다. → 더 이상 진행해도 결과는 큰 값이 나오기 때문
   2-3. queue에서 빼낸 원소와 1, 2, 3 숫자를 더했을 때 n보다 작으면 빼낸 원소와 숫자(1, 2, 3 중 하나)를 하나의 배열로 합쳐 queue에 다시 담는다.

코드는 다음과 같다.

 

import sys
from collections import deque

T = int(input())
for tc in range(T):
    n = int(input())
    queue = deque([[1], [2], [3]])
    answer = 0
    while queue:
        num = queue.popleft()
        if sum(num) == n: answer += 1; continue

        for number in range(1, 4):
            if sum(num) + number == n:
                answer += 1
                continue
            elif sum(num) + number > n:
                break
            else:
                queue.append(num + [number])
    print(answer)