백준: 12101 1, 2, 3 더하기 2

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

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

 

문제 풀이

 1, 2, 3을 활용하여 N을 구할 수 있는 경우의 수 중 K 번째의 수식을 출력하는 문제이다. 문제의 경우 N의 크기가 크지 않기 때문에 DFS로 백트랙킹하여 문제를 쉽게 풀 수 있다.

 

• 재귀 호출을 하면서 구한 수의 합이 N보다 크다면, 경우의 수를 추가하지 않고 중단한다.
• 만약 구한 수의 합이 N이 되었다면 카운트 하고, K가 되면 수식을 출력한다.
  • 이는 DFS의 경우 `1 + 1 + 1 + 1`, `1 + 1 + 2`, `1 + 2 + 1`과 같은 순서로 탐색을 진행하기에 가능하다.
• DFS를 통해 모든 경우의 수를 탐색하였음에도 답을 찾지 못한다면 -1을 출력한다.

 

코드

from sys import stdin


def dfs(idx, sum_num, check):
    global cnt
    # n보다 큰 경우 확인할 필요 없음.
    if sum_num > n:
        return

    if n == sum_num:
        # k번째 수를 찾기 위함
        cnt += 1
        if cnt == k:
            # 숫자+숫자+숫자+로 기록하므로, 마지막을 제거하고 출력.
            print(''.join(check)[:-1])
            exit(0)

    for i in range(1, 4):
        check.append(str(i) + '+')
        dfs(idx + 1, sum_num + i, check)
        check.pop()


if __name__ == '__main__':
    cnt = 0
    n, k = map(int, stdin.readline().split())
    dfs(0, 0, [])
    print(-1)