글 읽기 - 부분 수열 관련 문제, 왜 틀렸습니다가 나올까요?

(追記) (追記ここまで)

부분 수열 관련 문제, 왜 틀렸습니다가 나올까요?

1208번 - 부분수열의 합 2

choyj1127 2년 전 0

N이 최대 40이니 두 배열로 나누지 않으면 2^40의 시간 복잡도는 너무 크다는 글을 봐서 왼쪽과 오른쪽 배열로 나누어 각각의 부분 수열들의 합의 결과물을 구했습니다. 제출해보면 "틀렸습니다"가 나오는데 어디가 잘못되어서 틀린 건지 잘 모르겠습니다..

import sys
from collections import defaultdict
input = sys.stdin.readline
answer = 0
n, s = map(int, input().split())
arr = list(map(int, input().split()))
check = defaultdict(int) # 왼쪽 배열에서의 부분 수열들의 합 케이스들을 표시하는 딕셔너리
def subsequences_sums(left, right, pos):
 global answer, check
 sums = [] # 배열의 left~right-1 까지의 부분 수열들의 합 구하기
 for i in range(left, right):
 length = len(sums)
 for j in range(length):
 sums.append(sums[j]+arr[i])
 sums.append(arr[i])
 for v in sums:
 if pos == 0: # 왼쪽 배열인 경우
 check[v] += 1 # check
 if pos == 1: # 오른쪽 배열인 경우
 answer += check[s-v] # s-v의 값의 수를 더하기
subsequences_sums(0, n//2, 0) # 왼쪽 배열에서 부분 수열들의 합 구하기
subsequences_sums(n//2, n, 1) # 오른쪽 배열에서 부분 수열들의 합 구하기
print(answer)

mastershim 2년 전 1

반례입니다.

아마도 왼쪽 / 오른쪽 부분 수열들의 합을 구해서 왼쪽에서 s가 있는 경우, 오른쪽에 s가 있는 경우를 고려하지 않으신 거 같습니다.

input :
5 5
1 2 3 4 5
output :
2
 
correct ans :
3

choyj1127 2년 전 1

헉 그렇네요 덕분에 맞았습니다 감사합니다 !!

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC