[백준] 16938번 캠프 준비 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

---

---

---

💡 문제

알고리즘 캠프를 열려면 많은 준비가 필요하다. 그 중 가장 중요한 것은 문제이다. 오늘은 백준이를 도와 알고리즘 캠프에 사용할 문제를 고르려고 한다.

백준이는 문제를 N개 가지고 있고, 모든 문제의 난이도를 정수로 수치화했다. i번째 문제의 난이도는 Ai이다.

캠프에 사용할 문제는 두 문제 이상이어야 한다. 문제가 너무 어려우면 학생들이 멘붕에 빠지고, 문제가 너무 쉬우면 학생들이 실망에 빠지게 된다. 따라서, 문제 난이도의 합은 L보다 크거나 같고, R보다 작거나 같아야 한다. 또, 다양한 문제를 경험해보기 위해 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야 한다.

캠프에 사용할 문제를 고르는 방법의 수를 구해보자.

입력

첫째 줄에 N, L, R, X가 주어진다.

둘째 줄에는 문제의 난이도 A$_1$, A$_2$, ..., A$_N$이 주어진다.

출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

제한

• 1 ≤ N ≤ 15
• 1 ≤ L ≤ R ≤ 10$^9$
• 1 ≤ X ≤ 10$^6$
• 1 ≤ A$_i$ ≤ 10$^6$

---

💭 접근

이 문제는 백트래킹 알고리즘을 사용하여 문제에서 주어진 조건에 맞는 문제들을 뽑는 조합문제이다.

문제 수에는 제한이 없기 때문에 2문제부터 n문제까지 뽑는 경우의 수를 구한다.

for i in range(2, n + 1):
    cnt = i
    dfs(0, 0, a[-1], a[0], 0)

이후, 백트래킹 알고리즘을 사용하여 총 문제의 난이도의 합이 r을 넘지 않는 문제들에 대해서만 뽑는다.

for i in range(start, n):
    if total + a[i] <= r:
        dfs(i + 1, depth + 1, min(min_a, a[i]), max(max_a, a[i]), total + a[i])

마지막으로 문제의 난이도의 '최대-최소' 값이 x를 넘으면 정답에 +1을 해주면 된다.

if depth == cnt:
    if l <= total <= r and max_a - min_a >= x:
        ans += 1
    return

---

📒 코드

def dfs(start, depth, min_a, max_a, total):
    global ans

    if depth == cnt:
        if l <= total <= r and max_a - min_a >= x:
            ans += 1
        return
    
    for i in range(start, n):
        if total + a[i] <= r:
            dfs(i + 1, depth + 1, min(min_a, a[i]), max(max_a, a[i]), total + a[i])

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

ans = 0
for i in range(2, n + 1):
    cnt = i
    dfs(0, 0, a[-1], a[0], 0)
print(ans)

---

💭 후기

약간의 조건이 추가된 간단한 조합문제였다.

---

🔗 문제 출처

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

---