개발 블로그

문제 링크 : www.acmicpc.net/problem/16938

문제

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

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

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

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

입력

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

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

출력

캠프에 사용할 문제를 고르는 방법의 수를 출력한다.

접근 방법

2개를 뽑는다고 했을 때, {10, 30} 과 {30,10}은 같은 경우이므로 중복 조합 개념을 적용했다.

그리고 DFS를 호출할 때마다 문제의 난이도 합, 최대 난이도, 최소 난이도를 파라미터로 전달해서 조건 만족 여부 검사를 쉽게 할 수 있도록 했다.

//
//  BF_BOJ16938_캠프준비.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/04.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N,L,R,X;

vector<int> vec;
int answer = 0;
int visited[15] = {0};

void pickDFS(int toPick, int start,  int sum, int maxi, int mini){
        
    if(toPick==0){
        if((L<=sum && sum<=R) && (X<= maxi - mini)) {
            answer++;
        }
        return;
    }
    
    for(int i = start; i<vec.size(); i++){
        if(visited[i]==0){
            visited[i] = 1;
            pickDFS(toPick-1, i, sum+vec[i], maxi<vec[i] ? vec[i]:maxi, vec[i]<mini ? vec[i]:mini);
            visited[i] = 0;
        }
    }
}


int main(){
    
    cin >> N >> L >> R >> X;
    
    for(int i = 0; i<N; i++){
        int num;    cin>> num;
        vec.push_back(num);
    }
    
    for(int i = 2; i<=N; i++){
        pickDFS(i,0, 0, 0, 1000001);
    }
    cout << answer;

    return 0;
}

주의할 점

DFS 함수  안에 다음과 같이 인자를 설정하면 틀린 답이 출력된다. 

입력예제 2인 경우,

{10,30} 일때 maxi = 30, mini = 10으로 설정되고 그 다음 조합인

{10,25} 일 때 maxi = 25로 설정되어야 하는데, 이미 maxi = 30으로 설정되어 있어서 30이 인자로 전달되기 때문이다.

for(int i = start; i<vec.size(); i++){
        if(visited[i]==0){
            visited[i] = 1;
            if(maxi<vec[i]) maxi = vec[i];
            if(vec[i]<mini) mini = vec[i];
            pickDFS(toPick-1, i, sum+vec[i], maxi, mini);
            visited[i] = 0;
        }
}