백준: 16938 캠프 준비

문제

16938번: 캠프 준비

 

문제 풀이

 N개의 문제가 주어지고, 각각의 문제에 대한 난이도가 주어진다. 2개 이상의 문제를 선택할 때 모든 문제 난이도의 합은 L보다 크고, R보다 작어야 한다. 또한, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차는 X보다 크거나 같아야 한다.

 

문제를 풀기 위해서는 DFS를 통해 조합을 구하면 된다. DFS로 조합을 구하는 방법은 N과 M (2) 와 동일한 로직으로 풀면 된다. `itertools.combination`로 구하면 가지치기를 할 수 없어 시간초과가 발생할 것 같다.

 

코드

from sys import stdin
from math import inf


def dfs(score, idx, cnt, total_sum):
    global answer

    if cnt >= 2:
        if l <= total_sum <= r and score[MAX] - score[MIN] >= x:
            answer += 1

    for i in range(idx, n):
        if questions[i] + total_sum <= r:
            next_score = [min(score[MIN], questions[i]), max(score[MAX], questions[i])]
            dfs(next_score, i + 1, cnt + 1, questions[i] + total_sum)


if __name__ == '__main__':
    MIN, MAX = 0, 1
    answer = 0
    n, l, r, x = map(int, stdin.readline().split())
    check = [False] * n
    questions = list(map(int, stdin.readline().split()))
    dfs([inf, -inf], 0, 0, 0)
    print(answer)

 DFS를 통하여 탐색하는 경로를 추가할 때, r보다 큰 경우는 추가하지 않도록 하면 시간초과가 발생하지 않고 문제를 통과할 수 있다. 또한, 조합을 구하므로 `idx`를 현재 선택된 `idx`에서 1증가 시켜 중복으로 선택되지 않도록 하여야 한다.