코딩테스트 연습 - 타겟 넘버(DFS/BFS)(푸는중)

문제

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 이하인 자연수입니다.

 

---

풀이

문제를 이해하는데 한참 걸렸다. 너무 불친절한 문제라고 느껴진다.

 

n이 2이상 20이하인것 까지는 좋은데, 각 숫자가 1 이상 50이하라는 부분이 잘 이해가 가지 않았다.

 

예시로 주어진 배열은 [1, 1, 1, 1, 1]인데 그렇다면 모든 배열이 동일한 숫자가 n번 반복된 배열인건지, 아니면 각 숫자는 임의의 1 이상 50이하의 숫자인데 우연히 예시에서만 모두 1로 주어진건지 구분이 안간다. 

 

전자일때와 후자일때의 계산방법은 확연히 다를 것이기때문에 좀 더 세밀하게 정보를 제공해주는 문제였다면 더 좋았을 것 같다.

 

사실 전자의 경우가 좀 더 좁은 범위 인것 같고, 후자가 더 넓은 범위이기에 후자로 풀면 전자는 그냥 풀릴 듯 하다. 

 

하지만 구분을 해보고 싶으니 전자로 먼저 풀어보고 후자로도 풀어봐야겠다.

 

Case1. numbers가 모두 같은 숫자로 n번 반복되는 배열인 경우

예를들어 예시와 같이 numbers가 [1, 1, 1, 1, 1]로 주어졌을 경우에 나올 수 있는 조합는 

 

 ① 모두 양수인 경우     (값 =  5) -  1가지

 ② 하나만 음수인 경우  (값 =  3) -  5가지  (5C1)

 ③ 두 개가 음수인 경우 (값 =  1) - 10가지 (5C2)

 ④ 세 개가 음수인 경우 (값 = -1) - 10가지 (5C3)

 ⑤ 네 개가 음수인 경우 (값 = -3) -  5가지  (5C4)

 ⑥ 모두 음수인 경우     (값 = -5) -  1가지

 

이렇게 5개 중에 2개를 고르는 5C2 의 계산식은 (5x4)/(2x1)이고, 3개를 고르는 5C3은 (5x4x3)/(3x2x1)이다.

(참고로 양수, 음수 두가지로 5개 칸을 채우는 방법의 수는 2의 5제곱이다!)

 

어쨋든. 

 

그렇다면 저 중에 target인 3과 같은 값을 가지는 조합의 수는 5가지뿐이다. 

 

이렇게 구하는 코드를 짜보면 

 

numbers는 number가 n번 반복된 배열이라고 했을 때 아래와 같이 코드를 짤 수 있었다,

def solution(numbers, target):
    number = numbers[0]
    n = len(numbers)
    answer = 0

    def P(n, i):		# 조합의 수를 구하기 위한 함수 정의
        p = 1
        for j in range(n-i+1, n+1):
            if j > 0:
                p = p*j
        return p

    for i in range(n):
        t = i*(-1)*number + (n-i)*(+1)*number
        if t == target:
            answer = P(n, i)/P(i, i) 	
            break
    return answer

결과는...

예시로 준 테스트는 통과했지만...

빵점을 받았다 ㅋㅋ

 

---

Case2. numbers가 각기 다른 숫자로 n개의 원소를 가지는 배열인 경우

 

조금 쉽게 이해를 해보고자 임의의 테스트 케이스를 만들었다.

n은 동일하게 5인 numbers는 [1, 2, 3, 4, 5]이며 target은 동일하게 3으로 해보았다. 

다음의 세 가지 방법으로 3을 도출할 수 있었다.

-5+4+3+2-1 = 3
+5-4+3-2+1 = 3
+5+4-3-2-1 = 3

 

이걸 어떻게 코드로 도출해낼 지에 대해서는 딱히 생각이 안난다.