BOJ 12101 - 1,2,3 더하기 2 (Python)

S1, 백트래킹

문제

정수 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

이를 사전순으로 정렬하면 다음과 같이 된다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 1+3
• 2+1+1
• 2+2
• 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

풀이

• 백트래킹을 통해 현재의 값을 갱신해나가며 진행해준다.

from sys import stdin
n, k = map(int, stdin.readline().split())

arr = [1, 2, 3]
total = set()
def dfs(value, tmp):
    if value == n:
        total.add(tuple(tmp))
        return

    if value + 1 <= n:
        dfs(value + 1, tmp + [1])
    if value + 2 <= n:
        dfs(value + 2, tmp + [2])
    if value + 3 <= n:
        dfs(value + 3, tmp + [3])

dfs(0, [])

if len(total) < k:
    print(-1)
else:
    res = sorted(list(total))[k-1]
    print(*res, sep='+')