백준 12101번 파이썬 문제풀이(1,2,3 더하기 2)

---

이 문제를 해결하는데 있어서 백트래킹 조건을 검사할 때 인자로 바로 숫자들을 문자로 바꿔 문자열로 더해서 인자로 넘기는 방식과 리스트에 담아서 sum으로 구하는 방식 2가지로 구현해보았다. 2가지 모두 코드를 제시해놓겠다.

 

1. 리스트 이용

def dfs(depth):
    global count
    global check

    if check:  # 만약 check 변수가 true라면 전체 재귀 종료
        return

    if len(arr) > n:  # 만약 뽑은 수의 개수가 n보다 크다면 종료
        return

    if depth > 0:  # 1개 이상 뽑았다면
        if sum(arr) == n:  # 그 합이 n가 같다면
            count += 1  # 개수 1개 증가

        if count == k:  # 만약 그 개수가 k랑 같다면
            print('+'.join(map(str, arr)))  # 그 값을 출력한 후
            check = True  # 전체 재귀 종료를 위해 check값을 true로 변경 후
            return  # 리턴

    for i in range(1, 3 + 1):
        arr.append(i)
        dfs(depth + 1)
        arr.pop()


n, k = map(int, input().split())
count = 0
arr = []
check = False
dfs(0)
if not check:  # 만약 k랑 같은 조건을 만나지 못했다면
    print(-1)  # -1 출력

2. 문자열을 인자로 넘기는 방식

def dfs(depth, num):
    global count
    global check

    if check:
        return

    if len(num) > n:
        return

    if depth > 0:
        temp = 0
        for i in num:
            temp += int(i)
        if temp == n:
            count += 1

        if count == k:
            print('+'.join(num))
            check = True
            return

    for i in range(1, 3 + 1):
        dfs(depth + 1, num + str(i))


n, k = map(int, input().split())
count = 0
check = False
dfs(0, '')
if not check:
    print(-1)