[프로그래머스] Level2_타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

정답 코드

score = 0
number = []
target = 0
def dfs(sum, idx):
    global number, score, target
    if idx == len(number):
        if sum == target:
            score += 1
        return 0
    dfs(sum+number[idx], idx+1)
    dfs(sum-number[idx], idx+1)



def solution(numbers, tar):
    global target, number
    number = numbers
    target = tar
    dfs(0, 0)


    return score

 

 

틀린 코드

result = []


def dfs(check, idx, cnt, nums, target):
    if cnt == len(nums):
        calcul(check, nums, target)
        return

    for i in range(idx, len(check)):
        if not check[i]:
            check[i] = True
            dfs(check, i, cnt + 1, nums, target)
            check[i] = False



def calcul(check, nums, target):
    sum = 0
    for i in range(len(check)):
        if check[i]:
            sum += nums[i]
        else:
            sum -= nums[i]

    if sum == target:
        result.append(1)


def solution(numbers, target):
    check = [False for _ in range(len(numbers))]

    dfs(check, 0, 0, numbers, target)
    return (len(result))


print(solution([1, 1, 1, 1, 1], 3))

 

왜 이런 코드를 작성했을까??

내가 접근했던 해결방식을 쭉 나열해보자.
우선, 문제 자체는 바로 해석하고 풀이가 가능하다.
numbers에 있는 숫자를 5C1부터 - 5C5까지 True를 뽑는 경우의 수를 모두 계산해 주어(True는 +, False는-로 지정했다.)
target과 같다면 result에 +1을 하여 구하면 된다.


여기까지 한번에 생각이 났다면 다 푼 것이나 다름없다.
하지만 왜 틀렸었을까?

 

이 부분을 잘못 생각해줬다. 
이렇게 dfs를 호출한다면, 모든 경우의 수를 고려해준 것이라 생각했다...

왜 잘못 생각했던 것인지, 왜 그렇게 생각했는지 짚고 넘어가자.
그냥 외우는 것이 아니라, 원리를 이해하려고 노력해보자.

 

 

잘못 생각했던 부분

1. Base case - (재귀호출의 무한루프를 막아주기 위해 if문으로 멈추는 구문을 작성해야 하는데, 그 구간을 Base case라고 한다.)

dfs의 Base case는 if cnt == len(nums)로 설정해 주었다.
즉, 재귀호출하는 dfs가 멈추게 되는 조건에 len(nums)의 값이 되는데, 이 값이 1이라면,
check = True를 한개만 뽑았을 때인 5C1의 경우의 수가 뽑히게 된다.

그렇다면 이것은 왜 5C1의 경우의 수를 고려해준 것이 될까?
재귀호출 전에 check=True를 해놓고, 호출 이후에 check=False를 해주니, 
현재 i에 해당하는 check[i]에 True를 해주었다가, Base case에 걸릴때까지 경우의 수를 계산하게 된다.
재귀호출 이후 해당 check[i]는 False로 해주니, Base case에 걸리는 조건의 수만큼 고려해주는 것이 된다.

---
이거 나만 알아볼 수 있겠는데,,, 남에게는 어떻게 설명하면 좋을까?
이것도 한번 고민해보자.

 

 

여기까지 어떤 부분이 문제인줄 알았고, 정확히 이해했다면

틀린 코드의 풀이방식을 맞게 고칠 줄도 알아야 한다.

 

틀린 코드 수정 후 정답 코드

result = []

def dfs(check, idx, cnt, nums, target, baseCase):
    global count
    if cnt == baseCase:
        calcul(check, nums, target)
        return

    for i in range(idx, len(check)):
        if not check[i]:
            check[i] = True
            dfs(check, i, cnt + 1, nums, target, baseCase)
            check[i] = False



def calcul(check, nums, target):
    sum = 0
    for i in range(len(check)):
        if check[i]:
            sum += nums[i]
        else:
            sum -= nums[i]

    if sum == target:
        result.append(1)


def solution(numbers, target):
    check = [False for _ in range(len(numbers))]

    for i in range(len(check)):
        dfs(check, 0, 0, numbers, target, i)
    return (len(result))


print(solution([1, 1, 1, 1, 1], 3))