[백준/파이썬] 16938번 캠프 준비

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

16938번: 캠프 준비

문제 해석

N개의 문제

i번째 문제의 난이도는 Ai

2문제 이상 사용

문제 난이도의 합은 L보다 크거나 같고

R보다 낮거나 같아야함.

가장 어려운문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야함.

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

둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다.

→ 캠프에 사용할 문제를 고르는 방법의 수

---

코드

input = __import__('sys').stdin.readline

n, l, r, x = map(int, input().split())
arr = sorted(list(map(int, input().split())))
# 난이도를 오름차순 정렬시켜, 최소 난이도, 최대 난이도 갱신을 쉽게함.

ans = 0
def dfs(depth, idx, maxim, mini, diff):
    global ans
    if diff > r: return # 난이도의 합이 r보다 크면 안됨
    elif depth >= 2 and l <= diff <= r: # 선택된 문제가 2개 이상 and 난이도가 l과 r사이 
        if not(maxim == None or mini == None) and maxim - mini >= x: # 최고 난이도와 최저 난이도의 차이가 X이상
            ans += 1
    for i in range(idx, len(arr)):
        # 최소가 존재하지 않다면 (depth == 0) 최소값 지정
        # 최소가 존재하면 최소는 그대로, 최대 값만 갱신
        
        if mini == None:
            dfs(depth + 1, i + 1, arr[i], arr[i], diff + arr[i])
        else:
            dfs(depth + 1, i + 1, arr[i], mini, diff + arr[i])

dfs(0, 0, None, None, 0)
print(ans)

---

문제 풀이

 

백트래킹 dfs 가지치기 방법이 바로 떠올라서 해당 방법으로 풀었다.

dfs를 조합을 기반으로 구현하고, 모든 조건을 확인하며 가지치기 해주었다.

 

먼저 입력받은 arr을 오름차순 정렬한 뒤 가치지기 해주었다.

 

dfs(매개 변수 용도)

depth는 dfs 깊이, 즉 몇개를 선택하였는지에 대한 정보

idx는 조합을 위해 사용

maxim은 최대값 (arr을 오름차순 정렬해놓았기 때문에 항상 새로 선택되는 수가 최대값이다.)

mini는 최소값 (첫번째 선택 즉, depth가 0일때 선택된 값이 항상 최소값이다.)

diff는 난이도의 합. (선택될때마다 이 값이 선택된 값을 더해줌)

 

난이도의 합(diff)가 기준인 r 보다 크면 return (가지치기)

 

2개 이상 선택(depth)하고, 난이도(diff)가 l보다 크거나 같고, r보다 작거나 같고,

최고 난이도(maxim)와 최소 난이도(mini)의 차이가 x보다 크거나 같다면 ans += 1

 

가지치기 백트래킹 방식은 조건만 잘 구현해 최대한 많은 가지를 친다면 쉽게 풀 수 있을 것이다!

배열을 정렬시켜 인자에 넘기는 값을 최소화 시키는것이 핵심인 것 같다. (메모리 초과 방지, 배열 리스트는 절대 넘기면 안됨..)

이외에도 간단하게 조합론으로 풀 수 있고, 비트 마스킹 방법으로 풀 수 있는데.. 비트 마스킹은 아직 할 줄 모르기에..