[TIL] 99클럽 코테 스터디 9일차 TIL + 그리디

🌼 오늘의 문제 - 백준 2437. 저울

처음에는 이 문제를 직접 부분 집합을 모두 구하고, 빈 공간이 생기는 최소 숫자를 결과로 출력했다. 당연히(?) 시간 초과로 실패했다. 이렇게 직접 모두 구하는 방식이 아닐 거라고 생각했지만, 혹시나 하는 마음에 제출해 봤지만.. 그렇게 되었다. ㅎㅎ... 그래서 정답을 찾았고, 문제 풀이를 이해하는데 정말 오래 걸렸다. 코드는 단순한데, 그 풀이를 이해하는데 시간을 조금 썼다.

 

내일 다시 천천히 코드를 보면서 이해하는 시간을 가져봐야지!

""" 정답 코드 """
n = int(input())
arr = list(map(int, input().split()))


def solution2():
    arr.sort()

    target = 1
    for w in arr:
        if w <= target:
            target += w
        else:
            break

    print(target)


solution2()

 

그냥 남겨본 나의 첫 번째 풀이.. ㅎㅎ...

""" 시간 초과 났던 나의 첫 번째 풀이ㅎㅎ.. """
def subset_sum(arr):
    result = set()
    n = len(arr)

    # << 는 비트 연산자 - n만큼 비트를 움직임 2^n
    # arr 가 가질 수 있는 모든 부분집합
    for i in range(1 << n):
        total = 0

        for j in range(n):
            if i & (1 << j):
                total += arr[j]

        result.add(total)
    return result


def solution1():
    arr.sort()
    subset_sum = subset_sum(arr)

    i = 0
    while True:
        if not i in subset_sum:
            break
        i += 1

    print(i)
    

n = int(input())
arr = list(map(int, input().split()))

solution1()