백준 16938 캠프 준비 Python

🐸 문제 정보

16938번: 캠프 준비

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

12.43m

 

📝 풀이

시간복잡도 무조건 터질거라고 생각했는데 바로 성공해서 읭 한 문제였다.

문제 수가 15개 밖에 안되니까, 문제 내용대로 직관적인 백트래킹 함수를 작성했다.

 

1. (현재 인덱스, 현재까지의 합, 최소, 최대)를 인자로 전달하는 백트래킹 함수
2. 합이 L과 R 사이이고, 최대 - 최소가 X보다 크거나 같다면 res 갱신

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, l, r, x = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
a.sort()
res = 0

def bt(idx, cur, nv, xv):
    global res
    if (l <= cur <= r) and (x <= xv - nv):
        res += 1
    for i in range(idx + 1, n):
        bt(i, cur + a[i], nv, a[i])

for i in range(n):
    bt(i, a[i], a[i], a[i])

print(res)