[백준] 12101번 1, 2, 3 더하기 2

💡문제접근

• 백트래킹을 통해서 접근했다. 재귀함수를 작성하여 접근하는데 합이 n이면서 뽑은 수의 개수가 k개인 모든 경우를 따지지 않고 순서 변수인 cnt를 전역변수로 설정하고 합이 n이면서 순서 변수가 주어진 k와 일치하는지를 확인해서 답을 출력한다. 아니라면 -1을 출력한다.

💡코드(메모리 : 31120KB, 시간 : 44ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, k = map(int, input().strip().split())
cnt = 0
answer = []

def recursive(Sum, num):
    global answer, cnt
    if Sum > n:
        return
    if Sum == n:
        cnt += 1
        if cnt == k:
            print("+".join(map(str, num)))
            sys.exit(0)
    for i in range(1, 4):
        num.append(i)
        recursive(Sum + i, num)
        num.pop()

recursive(0, [])
print(-1)

💡소요시간 : 27m