더하거나 빼거나

본 문제는 스파르타 코딩에서 제공된 문제입니다.

Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

numbers = [1, 1, 1, 1, 1]

target_number = 3

항상 코드를 작성하기 전에 이 문제가 요구하는 것이 무엇인지, 어떤 방법으로 풀어나가야 할지에 대해서 생각을 해봐야한다. 일단 이 문제에서 원하는 것은 '숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.'이다.

그렇다면 이제 생각해야 될 부분은 '타겟 넘버에 비슷하게 만들면서 타겟넘버에 맞춰가야 하나?' or '현재 상황에서 나올 수 있는 모든 경우의 수를 구한 후 타겟넘버의 개수를 구해야 하나?'이다. 결론부터 말하자면 후자이다. 사실 이와 같이 경우의 수가 다양하게 나오는 문제들은 최적의 경우의 수만을 구하기란 쉽지 않은 방법이다. 어떤 공식이 존재하거나 경우가 적다면 가능할지 모르겠지만, 경우가 너무나 다양한 경우 그냥 모든 경우를 다 탐색한 후에 판단하는 것이 좋다.

그렇다면 이제 모든 경우의 수를 어떻게 풀어 나갈 것인가? 이 자체를 그림으로 생각해보면 트리로써, 가지를 뻗어나가는 형식으로 표현할 수 있다. 즉, 재귀적으로 풀어가는 것이 효율적으로 풀 수 있다는 것을 알 수 있다. 그렇다면 이제 코드를 보자.

---

result = [] #모든 경우의 결과를 저장하는 리스트


def cal_tar(arr, total): #재귀함수
    if not arr: #(종료 조건) 해당 리스트가 비어있다면
        result.append(total) #결과 리스트에 해당 결과를 저장
        return #해당 루트 종료
    cal_tar(arr[1:], total + arr[0]) #재귀적으로 들어가기1. 해당 값을 더하는 경우
    cal_tar(arr[1:], total - arr[0]) #재귀적으로 들어가기2. 해당 값을 빼는 경우


def check(numbers, target): #결괄를 구하는 코드
    cal_tar(numbers, 0) #재귀함수 호출, result 리스트를 구성하는 코드
    return result.count(target) #완성된 result리스트에서 target과 일치하는 요소의 개수 반환


print(check([1, 1, 1, 1, 1], 3)) #답:5
print(check([2, 3, 1], 0)) #답:2

먼저, 리스트를 받아와서 리스트의 첫 번째 요소를 현재까지 계산된 total값에 더해주거나 빼줘서 다른 재귀로 넘어가게 한다. 그러면서 리스트의 첫 번째 요소를 배제하고 리스트를 넘겨주며 이와 같은 과정들이 반복되게 한다. 마지막으로 리스트에 요소가 없다면, 즉 모든 요소를 더하거나 빼주었다면 그 결과 total을 결과들의 리스트인 result에 저장해준다. 그 후 result에 target과 동일한 결과를 가진 요소의 개수를 세어주면 끝난다.

---

사실 이문제는 어떻게 접근하고 푸는지만 파악한다면 그리 어려운 문제는 아니다. 하지만 그 과정까지가 좀 까다로울 수 있다. 나도 처음에는 모든 경우의 수를 참조해야겠다 라는 생각을 하지 못했다. 그래서 최적의 경우만을 찾으려고 하느라 시간을 낭비했었다. 결국 모든 문제는 위에서 언급했듯이 어떤 것을 요구하고 그것을 충족시키기 위해서 어떻게 접근해야 하는가가 핵심이다.