(Python/파이썬) - 백준(BOJ) 12101번 : 1, 2, 3 더하기 2

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

 

 

 

---

• 풀이 :

백트래킹 문제였습니다. 

재귀를 사용한 완전탐색의 개념에서 적절한 위치에 Pruning을 해 주어 효율성을 증가시키는 방법으로 구현하였습니다.

 

알고리즘의 흐름입니다.

 

1.  재귀함수의 매개변수인 n은 현재까지 더한 값이고 s는 더한 숫자들입니다.

 

2.  n이 N과 같아지면 현재까지 더한 숫자들을 answer 배열에 넣습니다. 만약 n이 N보다 커진다면 더이상 숫자를 더할 필요가 없으므로 함수를 종료합니다.

 

3. 재귀가 종료된 후 answer 배열을 오름차순 정렬하여 (문자열 형태로 저장하였으므로 사전순으로 정렬됩니다) K-1번째 원소를 주어진 출력 양식에 맞게 출력합니다.

 

 

 

 

---

• 소스코드 : 

N,K = map(int,input().split())
answer = []

def backTraking(n,s):
    if n == N:
        answer.append(s)
    if n > N:
        return
    for i in range(1,4):
        backTraking(n+i,s+str(i))

backTraking(0,"")
if K <= len(answer):
    print('+'.join(list(sorted(answer)[K-1])))
else:
    print(-1)