반응형
문제 정보
https://www.acmicpc.net/problem/1182
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
접근방법
수업시간에 부분집합 때문에 고생고생 문제를 풀고
부분집합을 연습하기 위해서 비슷한 문제를 풀어보았다.
크기가 양수인 부분
에 대한 해석이 어려웠는데 공집합을 제외하라는 의미로 알아듣고
원하는 sum 값이 0 일때 -1 해주는 방식으로 해결했다.
제출
def find(dep, subset):
global cnt
if dep == len(arr):
li.append(subset[:])
return
for i in range(2):
if not i:
subset.append(arr[dep])
find(dep + 1, subset)
subset.pop()
else:
find(dep + 1, subset)
n, key = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
li = []
find(0, [])
# print(li)
for i in range(len(li)):
if sum(li[i]) == key:
cnt += 1
if key == 0:
cnt -= 1
print(cnt)
추가
def find(dep, subset):
global cnt
if dep == len(arr):
li.append(subset[:])
return
for i in range(2):
if not i:
subset.append(arr[dep])
find(dep + 1, subset)
subset.pop()
else:
find(dep + 1, subset)
arr = [1,2,3,4] 라고 가정하고
함수는 dep(깊이) 와 subset(빈 리스트) 를 매개변수로 전달받는다.
for 문을 돌면서 subset 에 숫자를 넣어주는 경우 (i = 0) 넣어주지 않는 경우 (i = 1) 로 나눠서 생각한다.
재귀를 통해서 깊이를 1씩 증가시켜 주면서 인덱스 값을 이동시키면서 빈 리스트에 값을 넣어준다.
arr 의 길이와 깊이가 동일해지면 [:] 카피를 통해서 값을 전역변수 li 에 저장하고 return 을 통해서
호출 대기중인 함수 위치로 이동한다.
반응형
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 8979 올림픽 (파이썬) (0) | 2022.09.26 |
---|---|
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |
백준 1967 트리의 지름 (파이썬) (0) | 2022.09.21 |
백준 1181 단어 정렬 (파이썬) (0) | 2022.09.20 |
백준 2589 보물섬 (파이썬) (0) | 2022.09.14 |