(Python/파이썬) - 백준(BOJ) 16983번 : 캠프 준비

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

16938번: 캠프 준비

---

• 문제 : 

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

 

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

 

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

 

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

 

 

 

---

• 풀이 :

조합론 문제입니다. python의 combinations 모듈을 사용하면 간단하게 해결할 수 있지만

저는 비트마스킹을 이용한 백트래킹으로 해결하였습니다.

 

알고리즘의 흐름입니다.

 

1. 백트래킹 함수의 매개변수로 현재까지 난이도의 총 합인 s, 가장 낮고 높은 난이도인 min, max_score, 조합을 짜기 위해 이전까지 탐색한 인덱스를 담은 idx를 사용

 

2. 주어진 문제의 조건에 해당한다면 이 때의 visited값을 answer에 삽입한다. answer은 set이기때문에 자동으로 중복이 처리된다.

 

3. 비트마스킹을 사용하여 visited배열의 오른쪽에서부터 i번째 이진값이 0 (방문하지 않음) 이라면 방문처리하고 bt함수를 재귀호출한다. 호출 이후에 다시 미방문으로 변경하여 백트래킹의 독립시행을 보장해준다.

 

---

• 소스코드 : 

N,L,R,X = map(int,input().split())
A = list(map(int,input().split()))
visited = 0b0
answer = set()
def bt(s, min_score, max_score, idx):
    global visited
    if L <= s and max_score - min_score >= X:
        answer.add(visited)
    for i in range(idx, N):
        if visited & (1 << i) == 0:
            visited ^= (1 << i)
            if s + A[i] <= R: bt(s+A[i], min(min_score, A[i]), max(max_score, A[i]), i+1)
            visited ^= (1 << i)
if N > 1:
    bt(0, 10**6 + 1, -10**6-1, 0)
    print(len(answer))
else:
    print(0)