프로그래머스 - 타겟 넘버 (Python)

문제

코딩테스트 연습 - 타겟 넘버

 

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [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이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

코드

from itertools import *

def solution(numbers, target):
    answer = 0
    sub = (sum(numbers) - target)//2 #1

    numbers = [i for i in numbers if i <= sub] #2
    
    for i in range(1, len(numbers)+1):
        per = list(combinations(numbers, i))
        for j in per:
            if sum(j) == sub: #3
                answer +=1 
    
    return answer

 

풀이

numbers	target	return
[4, 1, 2, 1]	4	2

 

1. 모든 기호를 +로 가정하고, numbers의 총 합에서 target 값을 뺀 차를 구한다. (8 - 4 = 4)

2. 기호를 적절히 조합하여 총 합에서 sub만큼을 빼줘야 target 값으로 만들 수 있다는 것을 알 수 있다.

3. 위의 경우 합이 8이고, 4를 제외한 모든 원소를 빼면 합이 4가 아닌 0이 된다. (+4-1-2-1 = 0)

    그러므로 4를 제외한 나머지 원소들끼리의 합을 0으로 만들어야 하고, 그러려면 원소들의 조합의 합이 sub/2가 되어야 한다.

4. 이 문제에서는 target 값이 만들어지지 않는 경우는 없으므로 (합이 target이 되는 원소들이 반드시 존재하므로),

    원소들의 조합이 sub/2가 되는 경우의 수를 구하면 된다. (+4-1+2-1 = 4, +4+1-2+1 = 4)