[일간임무] - 타겟 넘버

figure 1a

Elapsed time : 10min

처음에는 Permutation이나 Combination 문제로 생각했습니다. (+)와 (-)로 만들 수 있는 모든 경우의 수를 먼저 찾고 각 합을 구하면 되는 문제인 줄 알았는데 그러면 너무 큰 시간이 필요합니다.

어떻게 접근하면 좋을지 몰라서 그냥 그림으로 그렸는데 바로 영감을 받을 수 있었습니다.

figure 1b

입력으로 받은 컨테이너의 첫 번째 원소부터 하나씩 빼거나 더하면 위와 같이 이진 트리로 그려집니다. 그리고 이런 이진 트리를 이용한 검증 방법을 구현하기 위해서 재귀를 선택했습니다. Iterative하게 구성을 하면 좋을 것 같은데, 경우의 수가 갈라지는 걸 구현을 못하겠습니다. 할 수 있는지도 잘 모르겠습니다. 아무튼 재귀를 이용하면 모든 경우의 수를 가지를 뻗으며 확인할 수 있습니다.