[BOJ] 캠프준비 in Python

문제 풀러 가기!

난이도: G5
사용한 알고리즘: Bitmask, 완전 탐색

G5에 랭크되어 있어 어느 정도 어렵겠지 했지만, 그렇지 않았습니다. 1일 알고리즘.. 이거로 힐링하고 있는데, 만족스럽지 않네요ㅜ

점점 골드가 골드가 아닌거 같은 이 느낌....

그래도 겸손하게 꾸준히 풀어야겠습니다.

문제 설명

그냥 문제를 선택하는 것을 bitmask로 결정하면 됩니다.

하지만 문제의 조건 상 문제를 2개 이상을 고르는 것이 약간 마음에 걸리네요.

물론 그러한 조건을 코드에 추가하지 않아도 통과가 되었으나, 좀 더 정확한 코드이기 위해서는 앞서 말한 조건을 추가시키는 것이 좋겠네요.

여튼 1이면 문제를 선택! 그렇지 않으면 선택하지 않는 것으로 생각했고 이를 순회하면서 문제의 조건에 충족되는 것만 count 해주면 끝납니다.

그러면 bitmask를 할 수 있는 이유는 n이 15로 값이 생각보다 크지 않기 때문입니다.

최대 15 * 2^15로 50만번 순회 끝에 문제를 풀 수 있습니다.

코드

import sys
input = sys.stdin.readline

n, l, r, x = map(int, input().split())
level = list(map(int, input().split()))

cnt = 0
for i in range(1 << n):

    c = 0
    for j in range(n):
        if i & (1 << j):
            c += 1
    
    if c < 2: continue

    l_s = 0
    min_l = int(10e9)
    max_l = 0
    diff = 0
    for j in range(n):
        if i & (1 << j):
            l_s += level[j]
            min_l = min(min_l, level[j])
            max_l = max(max_l, level[j])
            diff = max_l - min_l
    
    if not (l <= l_s <= r):
        continue

    if not x <= diff:
        continue

    cnt += 1

print(cnt)