[ 12101 ] [ Recursion ] 1,2,3 더하기 2

문제 설명

---

문제

정수 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
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

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

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

---

풀이 과정

1. 사전순으로 정렬된 리스트를 얻어야 하므로, Recursion으로 구현 할 때 현재 합에서 1->2->3 순으로 더하도록 Recursion을 진행한다.
2. Recursion을 진행한다.
   • 현재 사용한 숫자들에 1, 2, 3을 넣고, 사용한 숫자를 합계에 더해서 다음 Recursion 호출
   • Recursion을 진행하다 현재 합계가 n보다 커진다면 종료
   • n과 같다면 리스트에 추가하고 종료한다.
3. 2번 과정을 진행하면 결국 1,2,3의 합으로 나타내는 모든 방법이 정렬되어 있는 리스트를 얻게 된다.
   • 따라서, k-1번째 인덱스의 방법을 출력해주면 된다.
   • 이 때, k-1이 방법의 수보다 큰 경우가 있으므로, 이 때는 -1을 출력해준다.

---

소스 코드

n, k = map(int, input().split())

case = []
def dfs(numbers, sumation, target):
    global case

    if sumation == target:
        case.append(numbers)
        return
    if sumation > target:
        return

    for i in [1, 2, 3]:
        dfs(numbers + [i], sumation + i, target)

dfs([], 0, n)
if k - 1 < len(case):
    print("+".join(map(str, case[k-1])))
else:
    print(-1)