lv2 타겟 넘버

문제링크

• 타겟 넘버

문제 설명

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

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

코드

DFS 풀이

def dfs(i, numbers, target, tot):
    global cnt
    n = len(numbers)
    if i== n:
        if tot == target:
            cnt += 1
            
    else:
        dfs(i+1, numbers, target, tot + numbers[i])
        dfs(i+1, numbers, target, tot + numbers[i]*(-1))
            
def solution(numbers, target):
    global cnt
    cnt = 0
    dfs(0,numbers, target, 0)
    return cnt

 

중복순열

• 중복조합은 from itertools import combinations_with_replacement를 쓰는 반면 중복순열은 from itertools import product를 쓴다
• combinations_with_replacement(뽑을 곳, 반복횟수)을 써주기만 하면 되는 반면 product(뽑을 곳, repeat = 반복횟수)임 만약 product에서 repeat을 안쓰면 오류가 뜸 

ex)

from itertools import combinations_with_replacement

li = [1,2]
for com in combinations_with_replacement(li, 2):
    print(com)

>>>(1, 1)
   (1, 2)
   (2, 2)

from itertools import product

li = [1,2]
for pro in product(li,2):
    print(pro)

>>> TypeError

from itertools import product

li = [1,2]
for pro in product(li,repeat = 2):
    print(pro)

>>> (1, 1)
    (1, 2)
    (2, 1)
    (2, 2)

 

중복순열을 이용한 풀이

def solution(numbers, target):
    from itertools import product
    w = [-1,1]
    n = len(numbers)
    cnt = 0
    for per in  product(w, repeat = n):
        sol = 0
        for i in range(n):
            sol += per[i]*numbers[i]
        if sol == target:
            cnt +=1
    return cnt

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges