[C++] 백준 16938 - 캠프 준비

---

문제 이해 단계

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

16938번: 캠프 준비

N개의 문제가 나열되어 있고, 각 문제는 정수로 난이도가 표현되어 있다.
이 중에서 2문제 이상을 골라야 한다.

고른 문제 난이도의 합이 L 이상, R 이하가 되어야 하고
최댓값과 최솟값의 차이가 X 이상이어야 한다.

해당 조건을 만족하는 문제의 경우의 수는 총 몇 개인지를 고르는 문제

 

 

---

문제 접근 단계

문제의 조건부터 살펴보자. 

문제의 개수 N이 최대 15개밖에 안된다.
이 말은 탐색할게 몇 개 없어서 완전 탐색을 해도 된다는 소리다.

그리고 L과 R은 최대 10^9이라 int 자료형을 넘을 수 있는 위험한 값이긴 한데,
L과 R은 제한범위이기 때문에 해당 변수를 더해주는 일은 없다.

그래서 int를 사용해 줘도 될 것 같다.

X와 원소값 A는  10^6 이어서 딱히 특이사항은 없어 보인다.

 

실패한 접근법들

이 문제는 N이 15개밖에 되지 않기 때문에 다양한 방법으로 접근해 봤다.

처음에 접근해 본 것은 투포인터 방법이었다.
왜냐하면 중요한 것이 최댓값과 최솟값의 차이기 때문이었다.

그래서 2개의 포인터를 최솟값과 최댓값으로 잡고 움직이는 방식으로 했는데,
생각해 보니 투포인터는 연속된 값을 받을 때 사용할 수 있다.

그런데 여기서는 연속되지 않을 수도 있다.
무조건 1,2,3을 고르는 것이 아닌 1,3,5를 고를 수도 있기 때문이다.

두 번째로 생각해 본 것은 동적계획법(DP) 방식이었다. 
값들을 오름차순으로 정렬해 두고 DP [최솟값][최댓값] = 개수 이런 식으로 풀어나갈 생각이었다.

그런데 DP로 풀려면 x = k 일 때 값이 같음이 보장되어야 한다.

그런데 이 문제는 범위가 바뀔 때마다 최댓값이 바뀌기 때문에 답이 바뀔 수밖에 없다.
그래서 DP로도 풀 수 없다.

 

백트래킹

결국 사용할 수 있는 것은 백트래킹이었다.
N = 15밖에 안되기 때문 하나씩 따져보기 충분했다.

값들을 오름차순으로 정렬해 둔 뒤,
가장 작은 값부터 하나씩 올려가며 백트래킹을 실행하였다.

반복문을 통해 시작한 값보다 큰 값을 하나하나씩 갖는 경우를 모두 재귀호출한다.
재귀호출하는 과정에서 값(난이도의 합)을 더하는 과정을 반복한다.

이렇게 백트래킹을 반복하다가 난이도의 합이 L과 R 사이에 들어온다면
처음에 시작했던 최솟값과 현재 인덱스(값)를 최댓값으로 하여 차이를 확인한다.

차이가 X 이상이라면 성공한 경우의 수이기 때문에 정답+1을 하면 된다.

이때, 백트래킹을 끝내는 것이 아니라, 가능한다면 다음 문제를 호출해야 한다.
왜냐하면 난이도의 합이 R을 넘지 않는다면 또 다른 경우의 수가 나올 수 있기 때문이다.

최종적으로 백트래킹(재귀함수)이 끝나는 곳은 난이도의 합이 R을 초과했을 때이다.

이 과정을 모든 문제를 최솟값으로 하여 한 번씩 백트래킹하여 답을 구한다.

이제 문제 구현 단계에서 살펴보자.

 

 

---

문제 구현 단계

vector<long long> v;
bool visited[16] = {false,}; // 각 문제의 방문 확인
int ans = 0; // 가능한 경우의 수
int N,X,L,R;

// sIdx = 최솟값 인덱스, x = 현재 문제 인덱스, cnt = 현재 난이도의 합
void backTracking(int sIdx, int x, int cnt){
    if(cnt > R) return; // 현재 난이도의 합이 R을 초과하면 종료

    // 난이도의 정답 범위에 들어오면
    if(L <= cnt && cnt <= R){
        // 최대-최소가 X보다 크거나 같으면 정답+1
        if(v[x]-v[sIdx] >= X) ans++;
    }

    // 백트래킹
    for(int i = x+1; i <= N; i++){
        if(visited[i]) continue; // 이미 방문한 문제 패스
        visited[i] = true; // 방문 확인
        backTracking(sIdx,i,cnt+v[i]);
        // 해당 재귀함수의 백트래킹이 종료되면 다른 재귀함수가 사용할 수 있도록 방문체크 해제
        visited[i] = false;
    }
}

백트래킹을 구현한 함수이다.
최솟값이자 시작인덱스인 sIdx와 현재 인덱스 x, 그리고 현재 난이도의 합 cnt가 매개변수로 사용된다.

위에서 설명했던 대로 난이도의 합이 R을 초과하면 재귀함수를 종료한다.
그리고 정답범위에 들어오면 최댓값과 최솟값의 차이를 판단하여 X 이상이면 정답에 추가한다.

백트래킹에서 방문을 확인하는 visited 배열을 통해 방문했던 곳을 재방문하지 않도록 한다.

중요한 것은 밑에 백트래킹 이후에 visited [i] = false로 방문을 해제해 주는 것이다.

이는 한 경우의 수에 대한 백트래킹이 종료된 뒤, 여전히 방문이 체크되어 있으면
다른 백트래킹 때도 방문하지 못하기 때문에 사용이 끝나면 방문을 해제해 주는 것이다.

여기까지가 핵심 함수인 backTracking함수에 대한 설명의 끝이고
아래에 전체 코드를 올리고 끝내겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<long long> v;
bool visited[16] = {false,}; // 각 문제의 방문 확인
int ans = 0; // 가능한 경우의 수
int N,X,L,R;

// sIdx = 최솟값 인덱스, x = 현재 문제 인덱스, cnt = 현재 난이도의 합
void backTracking(int sIdx, int x, int cnt){
    if(cnt > R) return; // 현재 난이도의 합이 R을 초과하면 종료

    // 난이도의 정답 범위에 들어오면
    if(L <= cnt && cnt <= R){
        // 최대-최소가 X보다 크거나 같으면 정답+1
        if(v[x]-v[sIdx] >= X) ans++;
    }

    // 백트래킹
    for(int i = x+1; i <= N; i++){
        if(visited[i]) continue; // 이미 방문한 문제 패스
        visited[i] = true; // 방문 확인
        backTracking(sIdx,i,cnt+v[i]);
        // 해당 재귀함수의 백트래킹이 종료되면 다른 재귀함수가 사용할 수 있도록 방문체크 해제
        visited[i] = false;
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> L >> R >> X;
    v.resize(N+1);
    for(int i = 1; i <= N; i++) cin >> v[i];
    sort(v.begin()+1,v.end());
    if(N == 1) {
        cout << "0";
        return 0;
    }
    for(int i = 1; i <= N; i++){
        visited[i] = true;
        backTracking(i,i,v[i]);
        visited[i] = false;
    }
    cout << ans;
}

 

 

---

시행착오

한 시간 동안 못 풀어서 문제 분류를 힌트로 봤는데, 백트래킹이라고 했다.
그걸 보자마자 불현듯이 바로 풀이가 떠올라서 풀었더니 됐다.

처음에는 위에서 말한 것처럼 DP로 풀어보고, 투포인터로 풀어보는 등 삽질한다고 시간을 많이 썼다.
백트래킹을 안 떠 올린 건 아닌데, 백트래킹도 안된다고 생각했다. 왜 안된다고 생각했지?

최대 최솟값을 정하는 게 어려워서 그랬던 것 같다.

음.. 열심히 하자.

생활비..

https://toss.me/howudong

howudong님에게 보내주세요