BOJ 1182 부분수열의 합
3330 단어 2021.01.272021.01.27
https://www.acmicpc.net/problem/1182
시간 1초, 메모리 128MB
input :
- N S(1 ≤ N ≤ 20, |S| ≤ 1,000,000)
- 정수 (정수의 절댓값은 100,000을 넘지 않는다.)
output :
- S가 되는 부분수열의 개수를 출력
조건 :
- 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램
투 포인터를 이용하거나, 조합을 이용하는 방법이 존재할 거 같다.
나는 그냥 조합을 써서 합이 S이면 ans 값을 하나씩 증가시켰다.
import sys
from itertools import combinations
n, s = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
ans = 0
for i in range(1, n + 1):
for item in combinations(data, i):
if sum(item) == s:
ans += 1
print(ans)
투 포인터를 쓸 거라면 양수 리스트, 음수 리스트를 나누고.
양수의 모든 값을 더하고, cost를 표시하든지, 반대로 하든지 해서
근데 이렇게 해서 완전 탐색 하는 거긴 한데 ㅋㅋㅋㅋㅋㅋ 괜찮겠지 ...
Author And Source
이 문제에 관하여(BOJ 1182 부분수열의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1182-부분수열의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)