백준 14225 부분수열의 합

https://boj.kr/14225 

14225번: 부분수열의 합

비트마스크로 풀었다.

수열의 길이만큼 비트 개수를 정하고 모든 경우의 수를 비트가 꺼져있는지 켜져있는지 확인해서 그 합을 구해서 풀었다.

set 자료구조를 사용해서 1부터 (수열에 있는 모든 합 + 1 ) 까지 수를 넣어주고 비트가 켜져있는 수의 합을 빼주면서 값을 구했다. 왜 수열에 있는 모든 합 +1 이냐면 가장 작은 자연수를 구할 때 수열의 모든 합보다 1 큰 자연수가 정답일 경우가 있기 때문에 그렇게 했다.

import sys
input = sys.stdin.readline

N = int(input().rstrip())
arr = list(map(int, input().split()))
last = set(range(1, sum(arr)+2))

mask_end = 1 << N

def subset_sum(mask):
    result = 0

    i = 0
    while mask:
        if mask & 1:
            result += arr[i]
        i += 1
        mask = mask >> 1
    return result
            

for mask in range(1, mask_end):
    s = subset_sum(mask)
    if s in last:
        last.remove(s)

print(list(last)[0])

 

맞춘사람 코드를 보니 너무 신기하게 풀어서 다시 작성해봤다.

어떤 기법을 쓴게 아니고 그냥 똑똑하게 풀었다고 생각한다. 코드가 워낙 짧아서 말로 설명하는 것 보다 코드가 더 이해하기 쉬운것 같다.

import sys
input = sys.stdin.readline

N = int(input().rstrip())
arr = list(map(int, input().split()))

arr.sort()

p = 0
for i in range(N):
    if p + 1 < arr[i]: break
    p += arr[i]

print(p+1)

실행시간도 엄청나게 차이가 났다.

문제 풀이를 하면서 이런 방식의 코드를 생각해 낼 수 있을지는 모르겠다.