백준 - 부분수열의 합(feat.Python)

Murjune·2022년 5월 30일
0

백준

목록 보기
7/10

https://www.acmicpc.net/problem/14225

문제 요구사항

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오

문제 풀이

n의 범위가 20까지의 자연수이고, S를 이루고있는 수는 100,000보다 작거나 같은 자연수이므로 모든 경우의 수를 다 검색해 보는 브루트포스문제임을 파악했다.
문제 풀이방법은 간단하다.

  1. 모든 부분순열을 구하고, 그 부분순열의 합을 Array에 캐싱해둔다.
  2. Array를 순차탐색하면서 Array[i]값이 0일 때의 i를 출력한다.
  • 시간복잡도 : O(n * 2^n)
  • 시간복잡도 계산: 2^20 * 20 = 약 2000만의 연산

이 문제는 백트래킹, 비트마스킹, 순열과조합으로 풀 수 있을 것 같은데 비트마스킹과 순열과조합 2가지 방법으로 풀어봤다 :D

1번째 풀이: itertools의 combination 모듈 사용

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

2번째 풀이 : 비트마스킹 (연산이 좀 더 빠르다)

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
profile
열심히 하겠슴니다:D

0개의 댓글