백준: 1208 부분수열의 합 2

문제

1208번: 부분수열의 합 2

 

문제 풀이

 앞서 다룬 부분수열의 합 문제에서 N의 범위가 40으로 증가한 문제이다. 따라서 기존의 풀이는 이 문제에 적용할 수 없다. 시간 초과가 발생하기 때문이다. 이 문제는 한 번에 N에 대한 부분수열을 모두 구하는 것이 아닌, 수열의 좌/우측으로 나누어 부분적으로 구한 후에 좌측의 작은 값 + 우측의 큰 값부터 점차적으로 계산해 S와 만족하는지 찾게 되면 시간 안에 문제를 해결할 수 있다.

 

 

def dfs(idx, end_idx, subtotal, ret):
    if idx == end_idx:
        ret.append(subtotal)
        return

    dfs(idx + 1, end_idx, subtotal, ret)
    dfs(idx + 1, end_idx, subtotal + nums[idx], ret)

    return sorted(ret), len(ret)


if __name__ == "__main__":
    answer = 0
    n, s = map(int, stdin.readline().split())
    nums = list(map(int, stdin.readline().split()))

    left, len_l = dfs(0, n // 2, 0, [])
    right, len_r = dfs(n // 2, n, 0, [])
    
    # 아래 부분은 생략 

 부분수열을 구하기 위해 처음에는 위와 같이 DFS로 작성하여 부분수열의 합을 계산하였다. 질문 게시판에 보면 N이 40인 경우의 예시가 추가된 것을 알 수 있다. 

 

 위의 예시를 해당 코드로 돌려보면 아무리 기다려도 결과를 반환하지 않는다....😂 고민을 하고 다른 사람의 풀이를 참고한 결과, 절반을 나눈 후 좌측에 대한 부분 수열의 합을 구했다면, 우측에 대한 부분 수열의 합을 구하면서 답을 구하는 방법을 사용하는 것이 더 효율적이라는 것을 알 수 있었다.

 

 문제를 푸는 방법을 정리하자면 다음과 같다.

• 주어진 순열(수들)을 절반으로 나누어 좌측에 대한 부분수열의 합을 구하고 이를 카운트한다.
  • 딕셔너리를 사용하면, 정렬에 대한 부분도 처리할 필요가 없다.
• (S - 우측 부분수열의 합)이 현재 딕셔너리에 카운트된 게 있으면 정답으로 반영한다.
  • 만약, 딕셔너리에 카운트되지 않은 값을 얻고자 한다면 0이 반영된다.
• 해당 방식은 좌측, 우측을 구한 후에 다시 while문을 돌며 좌측과 우측의 합이 S를 만족하는지 체크하는 방식보다 효율적으로 처리할 수 있으며, 정렬에 대한 오버헤드도 없을 것으로 생각된다.

 

코드

from sys import stdin
from collections import defaultdict


def dfs(idx, end_idx, subtotal, direction):
    global answer

    if idx == end_idx:
        if direction == "right":
            answer += left[s - subtotal]
        else:
            left[subtotal] += 1
        return

    dfs(idx + 1, end_idx, subtotal, direction)
    dfs(idx + 1, end_idx, subtotal + nums[idx], direction)


if __name__ == "__main__":
    answer = 0
    n, s = map(int, stdin.readline().split())
    nums = list(map(int, stdin.readline().split()))
    left = defaultdict(int)

    dfs(0, n//2, 0, "left")
    dfs(n//2, n, 0, "right")

    print(answer if s != 0 else answer - 1)

 `defaultdict`를 활용하여 딕셔너리를 사용하게 되면 value의 기본 자료형을 지정할 수 있어, 별도의 예외처리가 필요 없다.