[백준_12101]_1,2,3더하기2_python

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

12101번: 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번째로 오는 식을 구하는 프로그램을 작성하시오.

문제 해결

1,2,3 숫자 3개를 사용하여 n을 만드는 조합을 구하여 k번째 오는 식을 출력하면 된다.

중복 조합은 back_tracking으로 구현하였고 k번째의 값이 성립하기 위하여 출력 사항에 '사전 순'이 명시되어있다.

 

import sys
input = sys.stdin.readline
n , k = map(int,input().split())
numbers = [i for i in range(1,4)]
res = []

def dfs(box):
    if sum(box) == n:    ##stop
        res.append(box)
        return
    if len(box) > n:       ##중복으로 들어가기 때문에 정수의값(1만넣었을때의 길이)
        return             ##을 초과하는 경우에 return
    for i in numbers:      ##재귀로 파고들기
        dfs(box+[i])
dfs([])
if len(res)<k:    #k번째 올만큼의 길이가 되지 않는경우
    print(-1)
    exit(0)
print('+'.join(map(str,res[k-1])))#map 을사용해 str형으로 바꿔준후 +간격으로 출력