백준/Python) 16938 캠프준비 - 백트래킹 풀이

💭 나의 접근 방법

---

 

가능한 경우의 수를 나열하여 문제를 어떻게 선택할지 고민하였다. 

정해진 범위내에 최선의 선택을 해야하기 때문에 백트래킹이 떠올랐다.

 

N개의 문제들을 나열하고 특정 숫자에서는 합이 R을 초과하게 되는데 이부분 이 후 부터는 백트래킹을 이어하지 않고 중단시키려고 하였다. 그런데 문제를 보니 N이 15개로 제한되어있어서 끝까지 수행해도 되겠다 싶었고, 백트래킹의 기본 틀대로 문제를 풀었다.

 

💡 결과

---

# 16938 캠프준비 G5
import sys
input = sys.stdin.readline
N,L,R,X = map(int,input().split())
arr = map(int,input().split())
arr = sorted(arr)
answer = 0

def backtrack(start,lst):
    global answer
    if sum(lst) > R:
        return
    elif sum(lst) >= L and len(lst)>=2:
        first, end = lst[0],lst[-1]
        if end - first >= X:
            answer += 1
    for i in range(start,N):
        lst.append(arr[i])
        backtrack(i+1,lst)
        lst.pop()
backtrack(0,[])
print(answer)

 

반복문

backtrack 함수에 for문을 시작으로 문제점수가 있는 arr리스트를 탐색한다.

DFS 기반인 backtrack()함수로 들어가 점수를 lst에 추가하게 된다. 

 

종료조건

종료조건은 lst의 합이 R보다 클때 backtrack을 빠져나오게 된다.

다만, 점수의 합이 L보다 크고 R보다 작을때 다음 점수가 들어와도 R보다 작을수 있는 경우가 있기때문에 elif 문에는 return을 두지 않는다.

 

 

 

💫 느낀점

---

N개의 개수가 많을 경우 시간 초과가 날수도 있을것 같아, 반복문을 끝까지 돌지 않아도 pop()을 하는 방법을 찾아봐야할것 같다.

백트래킹이 어렵다 싶으면 N과M문제를 다 풀어보면 많은 도움이 됩니당

 

 

 

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

16938번: 캠프 준비