[PS | 한 번에 맞자!] 백준 16938

0. 문제

캠프 준비

16938번: 캠프 준비

1. 문제 생각

처음에는 투포인터일까? 싶었다. 
하지만 투포인터는 각 요소가 모두 다를 때 효율적인데 입력값에서 배열이 [10, 10, 20, 10, 40] 으로 들어온다면 이는 별 효율이 없을 것 같았다.
이후 입력값이 고작 N<=15인 걸 보고 브루트포스, 그 중에서도 백트래킹이나 조합을 생각해냈다.

N=15일 때 가장 입력값이 크다고 가정했을 때 
각 배열의 요소가 들어가거나/안들어가거나 둘 중 하나라 고작 2**15 밖에 되지 않아 안전하다.

---

2. 문제 풀이 (종이)

---

3. 문제 구현

N,L,R,X = map(int,input().split())
Problem=list(map(int,input().split()))
ans=0

def backtracking(node, visited, List): 
    global ans
    List=sorted(List)
    if sum(List) >= L and sum(List) <= R and List[-1]-List[0] >= X: 
        # print(List)
        ans+=1 
        #return하면 안됨 . => 한 번 더 가야할 수도 있으니까
    for i in range(node+1, N): # 1 ~ N 까지
        if not visited[i]: # 중복 확인
            visited[i]=1
            backtracking(i, visited,List+[Problem[i]])
            visited[i]=0

visited=[0 for _ in range(N)]
backtracking(-1, visited, [])
print(ans)

---

4. 한번에 풀었는가? ㅠㅠX

무조건 한번에 풀 수 있을 줄 알았는데 
조건 만족 시 ans+=1 이후 return문을 써서 한 번 틀렸다.

다른 백트래킹 문제에서는 주로 조건을 딱 만족시키면 더이상 볼필요가 없어 return문이 많이 적용되지만 위의 상황에서는 만족시키고도 한 번 더 재귀하여 다른 노드에 방문하고도 또 만족시키는 경우가 있어 return문을 쓰지 않아야 한다.

---

5. 다른 사람 풀이

다른 사람들 풀이를 보니
위에서 볼 수 있듯 백트래킹의 가지치기(return문)가 사실상 쓰이지 않아 그냥 combination으로 모든 경우의 수를 다 판단하는 코드를 많이 볼 수 있었다.