백준 1208번 - 부분수열의 합 2

출처 : 1261번: 알고스 팟 (acmicpc.net)

1261번: 알고스팟

 

---

 

부분 수열의 합 2 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

11389

2551

1601

21.791%

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분 수열의 개수를 출력한다.

 

---

[ 문제 해설 ]

 

 

그림으로 설명하겠음.

 

그림 1 - 문제 풀이 아이디어

그림 2 - 문제 풀이 아이디어

 

# 참고로 합이 3(key)이 되는 경우의 수가 4(value)가 있고, 합이 2(key)가 되는 경우의 수 5(value)가 있다면 더해서

5가 되는 경우의 수는 4*5= 20입니다.

 

 

---

[ 코드 ]

 

import sys
from itertools import combinations
from collections import defaultdict

n, s = map(int, sys.stdin.readline().split())
m = list(map(int, sys.stdin.readline().split()))

left = m[:n // 2]
right = m[n // 2:]

leftTotal = defaultdict(int)
rightTotal = defaultdict(int)
leftTotal[0] = 1
rightTotal[0] = 1

for i in range(1, len(left) + 1):
    print(list(combinations(left, i)))
    for com in combinations(left, i):
        leftTotal[sum(com)] += 1

for i in range(1, len(right) + 1):
    for com in combinations(right, i):
        rightTotal[sum(com)] += 1

# 계산할때는 키만 이용할거기 때문에
leftSumNum = sorted(leftTotal.keys())
rightSumNum = sorted(rightTotal.keys())

print(leftTotal)

res = 0
left = 0
right = len(rightSumNum) - 1
while left < len(leftSumNum) and right >= 0:
    if leftSumNum[left] + rightSumNum[right] == s:
        res += (leftTotal[leftSumNum[left]] * rightTotal[rightSumNum[right]])  # value * value 형식
        left += 1
        right -= 1
    elif leftSumNum[left] + rightSumNum[right] > s:
        right -= 1
    else:
        left += 1

if s == 0:
    res -= 1

print(res)

 

---

후기

 

복습을 하면 어렵다고 느꼈던 문제도

쉽게 느껴집니다.

복습 항상 필수라는 것을 여실히 느끼네요