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

https://www.acmicpc.net/problem/12101

12101번: 1, 2, 3 더하기 2

 

문제설명

재귀함수를 사용하는 대표적 백트래킹 문제이다.

1,2,3 세 종류의 숫자만을 합하여, 정수 n을 만들어야하는 문제다.

가능한 모든 식 중, 사전순으로 k번째 오는 식을 출력해주면 된다.

 

코드

input=__import__('sys').stdin.readline
li=[]
n,k=map(int,input().split())
th=0
def go(li):
    global th
    global ans
    if sum(li) == n:
        th += 1
        if th == k:
            ans = li.copy()
        return
    elif sum(li) > n:
        return

    for i in (1,2,3):
        li.append(i)
        go(li)
        li.pop()
ans=[]
go([])
if len(ans)==0:
    print(-1)
else:
    print('+'.join(map(str,ans)))

 

문제풀이

for i in (1,2,3) 해당 반복문을 통해, 계속해서 숫자를 리스트에 추가해준다.

그러다가 리스트에 담긴 수들의 합이 n과 같을 때 해당 문제의 조건에 만족하므로, 변수 th를 1씩 늘려주고 return 시킨다.

(리스트 원소의 총합이 n보다 커지는 경우는 문제의 조건에 해당되지 않으므로, 단순히 return만 시킨다.)

th가 k와 같을 때는 문제에서 요구하는 k번째의 식을 의미한다. 그러므로 그 답을 새로운 ans 리스트에 복사하고 return 시키면 된다.

go함수를 다 끝내고 다시 for문으로 돌아왔을때는, 이전에 리스트에 새로운 원소를 집어넣었으므로(append) 다시 빼주는 pop의 과정도  필요하다. 

최초로 빈 리스트를 인자로 넣었던 go함수가 끝나면, ans에는 정답으로 출력해야 할 숫자의 리스트가 담겨있을 것이다.

문제에서 요구하는 출력 형식에 맞게 출력해주면 된다.

하지만 만족하는 식이 아예 없어서 ans이 빈 리스트일 수 있으므로, 그럴 경우에는 -1을 출력해준다.