[백준] 1, 2, 3 더하기 2 (12101) - python

문제 링크 : https://www.acmicpc.net/problem/12101

문제 요약

정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전순으로 정렬했을 때 k번째로 오는 식을 나타내는 문제입니다.

 

풀이

문제 풀이를 위해 DFS(깊이 우선 탐색) 알고리즘을 사용했습니다. 각 조합에 가장 작은 수인 1을 우선으로 추가해 주면서 DFS를 진행하게 된다면 최종 리스트에는 정렬된 값이 순서대로 들어있기 때문에 효율적으로 문제를 해결할 수 있습니다.

 

정답 코드

import sys
input = sys.stdin.readline

def dfs(nums, n, numbers):
    sumNums = sum(nums)
    if sumNums == n:
        numbers.append(nums)
    elif sumNums > n:
        return
    if len(nums) > n:
        return
    for i in range(1, 4):
        dfs(nums + [i], n, numbers)

def main():
    n, k = map(int, input().split())
    numbers = []
    dfs([], n, numbers)
    if len(numbers) < k:
        print('-1')
    else:
        print('+'.join(map(str, numbers[k-1])))
    return

if __name__ == "__main__":
    main()

 

리뷰

처음 BFS 함수를 작성했을 때는 elif 문을 작성하지 않고 답을 작성했습니다. 그래도 코드가 통과되는 모습을 보고 더 생각하지 않으려고 했는데 소요시간이 생각보다 많이 나오는 것 같아서 필요 없는 연산을 줄여주는 방향으로 코드를 수정하게 되었습니다. 이러한 요인들이 더 복잡한 문제에서는 시간문제로 이어질 수 있기 때문에 유의해서 풀어야겠다고 생각했습니다.