[python]1182. 부분수열의 합

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

 

암생각 없이 하다가 틀렸다.

예제만 보고 아 세 숫자를 골라서 부분수열을 이루는 거구나 라고 혼자 착각을 하고 풀었다.

 

import sys
number, integer = map(int, sys.stdin.readline().split()) #개수와 정수를 받기
num_list = list(map(int, sys.stdin.readline().split())) #정수들 입력
case = 0 #경우의 수
a=0
for b in range(a+1, number-1): #pointer b
    for c in range(b+1, number): #pointer c
        if num_list[a] + num_list[b] + num_list[c]== integer:
            case +=1
    if a == number-2:
        break
    else:
        a+=1
 
print(case)
 

 

그런 결과.

 

ㅎㅎ

그래서 차근 차근 다시 읽어봤는데 부분수열이 내가 생각했던 부분수열이 아님을 깨달았다..

에를 들어 크기가 3인 정수들이 1, 2, 3이 주어졌을 때,

 

 

이렇게 고려를 해야한다는 것이다.

이 문제에서는 숫자들을 조합하는데 개수에 대한 조건이 없기 때문에 개수도 따로 정해지지 않은 것을 알 수 있다.

그래서 

 

from itertools import combinations
import sys
number, integer = map(int, sys.stdin.readline().split()) #개수와 정수를 받기
num_list = list(map(int, sys.stdin.readline().split())) #정수들 입력
case = 0 #경우의 수
for i in range(1, number+1): #부분 수열을 구성할 정의 개수
    subnet_list = list(combinations(num_list, i))
    for subnet in subnet_list:
        print(subnet)
        if sum(subnet) == integer:
            case+=1
print(case)

 

 

www.acmicpc.net/problem/1182