[Python - Backtracking, Dynamic Programming] 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의 합으로 나타내는 방법의 수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

1, 2, 3을 사용해서 만들 수 있는 경우를 모두 구하는 문제. 다이나믹 프로그래밍과 백트래킹 둘 중 하나를 사용해서 풀이할 수 있다.

 

다이나믹 프로그래밍을 떠올리게 된 방법은, 5는 4에서 1을 더한 것이고 3에서 2를 더한 것이며, 2에서 3을 더한 것으로 볼 수 있기 때문이다. 즉, 이전의 결과를 메모리에 저장해 계속해서 사용하여 풀 수 있었다.

 

백트래킹은 1을 더하는 경우와 2를 더하는 경우, 3을 더하는 경우 총 세 가지 선택지가 계속해서 주어져 탐색하기 때문에 백트래킹을 사용할 수 있었다.

👨‍🏫 문제 풀이

📄 전체 코드 1️⃣

from sys import stdin
input = stdin.readline

T = int(input())


def solve(k):
    global ans
    if k <= 0:
        if k == 0:
            ans += 1
        return

    solve(k - 1)
    solve(k - 2)
    solve(k - 3)


for _ in range(T):
    ans = 0
    solve(int(input()))
    print(ans)

📄 준비

from sys import stdin
input = stdin.readline

T = int(input())
for _ in range(T):
    ans = 0
    solve(int(input()))
    print(ans)

입력이 많으므로 빠르게 입력을 받도록 한다.

 

정답을 입력받을 ans 변수를 두었다.

📄 풀이

def solve(k):
    global ans
    if k <= 0:
        if k == 0:
            ans += 1
        return

    solve(k - 1)
    solve(k - 2)
    solve(k - 3)

재귀를 종료하는 조건은 두 개가 있다.

 

합이 주어진 값과 같은 경우와, 주어진 값보다 커지는 경우이다. 둘 모두 재귀를 마쳐야 하기 때문에 if문을 위와 같이 작성했다.

 

그런 후에, 세 가지 재귀를 들어간다. 1을 더하는 경우, 2를 더하는 경우, 3을 더하는 경우.

📄 전체 코드 2️⃣

import sys
n = int(sys.stdin.readline())

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(4, 12):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

for _ in range(n):
    num = int(sys.stdin.readline())
    print(d[num])

📄 준비

import sys
n = int(sys.stdin.readline())

d = [0] * 12
d[1] = 1
d[2] = 2
d[3] = 4

입력이 많으므로 빠르게 입력을 받도록 한다.

 

dp 테이블을 구성하기 전에 값을 먼저 받았다. 왜냐하면, 마이너스 인덱스로 값이 이상하게 저장되는 것을 방지하기 위함이다. 1을 더하는 경우, 2를 더하는 경우, 3을 더하는 경우를 위해서 이전의 경우를 탐색해야 한다. 그런데 기준 값이 2인 상태에서 1, 2, 3을 더한다고 하면, d[i - 3]이 d[-1]로 되어서 정답을 얻을 수 없다.

📄 풀이

for i in range(4, 12):
    d[i] = d[i - 3] + d[i - 2] + d[i - 1]

for _ in range(n):
    num = int(sys.stdin.readline())
    print(d[num])

미리 값을 저장해두고 각 반복에서 값을 출력한다.

📌 총평

의외로 백트래킹으로 3분만에 풀었다. 대박