https://www.acmicpc.net/problem/14225
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오
n의 범위가 20까지의 자연수이고, S를 이루고있는 수는 100,000보다 작거나 같은 자연수이므로 모든 경우의 수를 다 검색해 보는 브루트포스
문제임을 파악했다.
문제 풀이방법은 간단하다.
- 모든 부분순열을 구하고, 그 부분순열의 합을 Array에 캐싱해둔다.
- Array를 순차탐색하면서 Array[i]값이 0일 때의 i를 출력한다.
이 문제는 백트래킹
, 비트마스킹
, 순열과조합
으로 풀 수 있을 것 같은데 비트마스킹과 순열과조합 2가지 방법으로 풀어봤다 :D
from itertools import combinations
import sys
input = lambda : sys.stdin.readline().rstrip()
# 시간 복잡도 2^20 = 1_000_000 * 20 = 약 2000만
n = int(input()) # 1 ~ 20
# nums의 원소는 100,000보다 작거나 같은 자연수
nums = list(map(int,input().split()))
cache = [0]*(2_000_000 + 1)
# 숫자 배열 2_000_000
for i in range(1,n+1):
for arr in list(combinations(nums,i)):
cache[sum(arr)] = 1
for i in range(1,2_000_000 + 1):
if cache[i] == 0:
print(i)
break
from itertools import combinations
import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input()) # 1 ~ 20
nums = list(map(int,input().split()))
cache = [0]*(2_000_000 + 1)
for i in range(1, 1<<n): # 2^n - 1 의 경우의 수
sum = 0
for j in range(0, n): # 0 ~ n 자리수
if(i & 1<<j):
sum += nums[j]
cache[sum] = 1
for i in range(1,2_000_000 + 1):
if not cache[i]:
print(i)
break