1182번: 부분 수열의 합

1182번: 부분수열의 합

 

N개의 정수가 주어질 때, 크기가 양수인 부분수열 중 해당 부분수열의 합이 S가 되는 경우의 수를 구하는 문제.

 

문제의 설명이 약간 부족한 면이 있는 것 같다.

만약 N개의 정수 중 같은 숫자가 주어질 경우에는 어떻게 해야 하는지 명확하게 나와있지 않다.

일단 같은 숫자도 부분 수열에 포함될 수 있다고 생각하고 문제를 풀었다.

 

---

# 1182번: 부분수열의 합

n, s = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 부분수열의 합이 S가 되는 경우의 수
answer = 0

result = []
visited = [False] * n

def backTracking(num, temp_sum):
    # print(result, temp_sum)
    if len(result) > 0 and temp_sum == s:
        global answer
        answer += 1
        return
    
    for i in range(num, n):
        if not visited[i]:
            result.append(arr[i])
            visited[i] = True
            backTracking(i+1, temp_sum + arr[i])
            visited[i] = False
            result.pop()


backTracking(0, 0)
print(answer)

 

처음에는 이렇게 풀었다.

백트래킹을 돌면서, 만약 temp_sum이라는 값이 0이고, result(부분수열)의 길이가 0보다 큰 경우에 answer를 증가시켜준다.

이렇게 풀 경우, 57퍼센트 쯤에서 틀렸습니다가 나왔다.

 

반례를 못찾겠어서 구글링을 통해 반례를 찾았다.

만약 

5 0

0 0 0 0 0

이 주어진 경우 답은 31인데,

내 코드는 5가 나왔다.

 

문제가 되는 라인은 answer을 증가시켜주고 난 다음 return이었다.

return을 하게 되면, 그 다음에는 탐색하지 않고 잘못된 가지치기를 하기 때문에, 

0

0

0

0

0

이 5가지만 답으로 나오는 것이다.

 

그래서 return문을 빼주니, 통과했다.

# 1182번: 부분수열의 합

n, s = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 부분수열의 합이 S가 되는 경우의 수
answer = 0

result = []
visited = [False] * n

def backTracking(num, temp_sum):
    # print(result, temp_sum)
    if len(result) > 0 and temp_sum == s:
        global answer
        answer += 1
        # return
    
    for i in range(num, n):
        if not visited[i]:
            result.append(arr[i])
            visited[i] = True
            backTracking(i+1, temp_sum + arr[i])
            visited[i] = False
            result.pop()


backTracking(0, 0)
print(answer)

 

 

---

 

글 읽기 - 고수님들 차이점 명확히 알고싶습니다.

위 링크에서 내 코드의 문제점을 찾을 수 있었다.

 

 

 

---

코드 수정

 

그리고 사실 visited 리스트를 굳이 사용할 필요는 없다.

 

# 1182번: 부분수열의 합

n, s = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 부분수열의 합이 S가 되는 경우의 수
answer = 0

result = []

def backTracking(num, temp_sum):
    if len(result) > 0 and temp_sum == s:
        global answer
        answer += 1
    
    for i in range(num, n):
        result.append(arr[i])
        backTracking(i+1, temp_sum + arr[i])
        result.pop()


backTracking(0, 0)
print(answer)

 

이렇게 해도 답이 나오고, 코드를 더 간단하게 만든다면, 

# 1182번: 부분수열의 합

n, s = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 부분수열의 합이 S가 되는 경우의 수
answer = 0

result = []

def backTracking(num):
    if len(result) > 0 and sum(result) == s:
        global answer
        answer += 1
        # return
    
    for i in range(num, n):
        result.append(arr[i])
        backTracking(i+1)
        result.pop()


backTracking(0)
print(answer)

 

이렇게만 해줘도 된다.