Funcia
Lv.2bitsetdpknapsack

사탕 봉지 똑같이 나누기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

형제가 할머니께 사탕 봉지 NN개를 받았습니다. i번 봉지에는 사탕이 nums[i]개 들어 있고, 봉지는 뜯지 않고 통째로 나눠야 합니다.

모든 봉지를 빠짐없이 두 사람에게 나누어 주어 두 사람이 받은 사탕 수가 정확히 같게 만들 수 있으면 true, 없으면 false를 반환하세요.

입출력 예

numsresult
[1, 5, 11, 5]true
[1, 2, 3, 5]false
[3, 3, 3, 4, 5]true

입출력 예 설명

예 1 — [11]과 [1, 5, 5]로 나누면 둘 다 11개입니다.

예 2 — 사탕이 모두 11개라 똑같이 나눌 수 없습니다.

예 3 — [3, 3, 3]과 [4, 5]로 나누면 둘 다 9개입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → bool

제한 사항

  • 1≤N=1 \le N = nums.length ≤200\le 200
  • 1≤1 \le nums[i] ≤100\le 100

기대 복잡도

시간
O(N * S)
공간
O(S)

입출력 예

nums기대 출력
[1,5,11,5]true
[1,2,3,5]false
[3,3,3,4,5]true

힌트

힌트

전체 합 SS가 홀수면 바로 false입니다. 짝수라면 "합이 정확히 S/2S/2가 되는 봉지 묶음이 있는가?"라는 문제로 바뀝니다.

봉지마다 넣을지 말지를 모두 시도하면 2N2^N가지라 효율성 테스트를 통과할 수 없습니다. 대신

  • can[s] = "지금까지 본 봉지 몇 개로 합 s를 만들 수 있는가"

를 두고, 봉지 x를 볼 때마다 s를 큰 쪽부터 내려가며 can[s] |= can[s - x]로 갱신하세요(작은 쪽부터 돌면 같은 봉지를 두 번 쓰게 됩니다). 전체 O(N⋅S)O(N \cdot S)입니다. 불리언 배열 대신 비트셋(can |= can << x)을 쓰면 한 번에 여러 칸을 처리할 수 있어 훨씬 빨라집니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4013판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.