개발 블로그

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

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

배열을 char 형으로 설정해서 string의 push_back(), 

//
//  DFS_BOJ2210_숫자판점프.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

char map[5][5];
//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

vector<string> strVec;
void DFS(int r, int c, int toPick, string str){
        
    if(toPick==0){
        if(find(strVec.begin(), strVec.end(), str) == strVec.end()){
            strVec.push_back(str);
        }
        return;
    }
    
    for(int i = 0; i<4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr<0 || nr>=5 || nc<0 || nc>=5) continue;
        
        str.push_back(map[nr][nc]);
        DFS(nr, nc, toPick-1,str);
        str.pop_back();
    }
}

int main(){
    
    for(int i = 0; i<5; i++){
        for(int j = 0; j<5; j++){
            cin >> map[i][j];
        }
    }
    
    for(int i = 0; i<5; i++){
           for(int j = 0; j<5; j++){
               DFS(i,j,6, "");
           }
    }

    cout << strVec.size();
    
    return 0;
}

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

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작거나 같은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

접근 방법

정수 A를 string으로 형변환 한 뒤, 각 문자를 vector에 넣고 DFS를 돌려서 완전 탐색을 해 주었다. 

DFS를 돌면서 vector안의 각 요소를 str에 push_back()으로 붙이고 pop_back()으로 빼주었다.

A의 자리수만큼 수를 만들었으면 정수형으로 다시 바꾼뒤 문제의 조건을 만족하는지 확인한다.

//
//  BF_BOJ16943_숫자재배치.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/05.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int visited[10] = {0};
vector<char> vec;
int A,B;
string strB;
int maxi = 0;
int answer = 0;
void DFS(int toPick, string str){
    
    if(toPick==0){
        int num = stoi(str);

        if(num!=A && num<B){        //B보다 작으면서
            if(maxi<num) {          //그 중 가장 큰 값
                maxi = num;
                answer = num;
            }
        }
    }
    
    for(int i = 0; i<vec.size(); i++){
        
        if(visited[i]==0){
            if(str.length()==0 && vec[i]=='0') continue;        //처음 0이 오면 안됨
            visited[i] = 1;
            str.push_back(vec[i]);
            DFS(toPick-1, str);
            str.pop_back();
            visited[i] = 0;
        }
    }
}


int main(){
    
    cin >> A >> B;
    
    string strA = to_string(A);
    string strB = to_string(B);
    int nLen = (int)strA.length();
    
    for(int i = 0; i<nLen; i++){
        vec.push_back(strA[i]);
    }
    
    DFS(nLen, "");
    if(answer==0) answer=-1;
    cout << answer ;
    
    return 0;
}

문제 링크 : 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;
        }
}

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

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

접근 방법

주의할 점 : B에 포함된 원소는 10^18 보다 작거나 같은 자연수이므로 자료형을 long long 으로 해줘야 한다. int 형으로 하면 출력초과나 틀렸습니다가 나온다. 

주어진 조건대로 직관적으로 풀어보았다.

1. 주어진 수열 B의 첫번째 요소를 x로 설정한다.

1-1. x곱2 연산을 한 결과가 (수열 B에 있고 x로 설정한 적이 없으면) 수열 A에 push 하고 DFS를 호출한다. 

1-2. x곱2 연산을 한 결과가 (수열 B에 없거나 x로 설정한 적이 있으면) 나3 연산을 진행한다.

     1-2-1) x가 3의 배수이고, x/3이 수열 A에 있고 ,x/3을 x로 설정한 적이 없으면 수열 A에 x/3을 push 하고 DFS를 호출한다. 

이 과정을 반복해서 수열 A의 크기가 N이 되면 DFS를 빠져나갈 때 바로 빠져나가기 위해 iscontinue를 false로 설정한 뒤 수열 A의 원소를 출력한다. 

예로 A = {4 8 6 3 12 9} 이고 x=4로 설정한 후 실행했다고 해보자.

4*2 = 8 -> 8은 수열 A에 존재하고 x=4이므로 visited한 적 없으므로 수열A에 8을 push하고 DFS를 호출한다. 

8*2 = 16은 수열 A에 존재하지 않으므로 16을 수열 A에서 pop 하고 DFS를 빠져나간다.

다시 8에 대해 나3 연산을 수행해본다. 8은 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

다시 4에 대해 나3연산을 수행해본다. 4도 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

이제 x=8로 설정하고 위와 같이 반복한다.

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int visited[100] = {0};
int N;

pair<bool, int> isIn(long long num){					
    for(int i = 0; i<N; i++){
        if(vecB[i]==num) return make_pair(true, i);		//<해당 숫자가 있는지,수열 B에서 몇번째 인덱스인지>
    }
    return make_pair(false, -1);
}

bool iscontinue = true;
void DFS(long long x, int cnt){
    
    if(cnt==N){
        iscontinue = false;
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        printf("\n");
        return;
    }
    
    //곱2
    pair<bool, int> p = isIn(2*x);
    if(p.first==true && visited[p.second]==0){
        visited[p.second] = 1;
        vecA.push_back(x*2);
        DFS(x*2, cnt+1);
        if(iscontinue){
            vecA.pop_back();
            visited[p.second] = 0;
        }else return;
       
    }

    
    //나3
    if(x%3 == 0){
        pair<bool, int> p2 = isIn(x/3);
        if(p2.first==false) return;
        else if(p2.first==true && visited[p2.second]==0){
            visited[p2.second] = 1;
            vecA.push_back(x/3);
            DFS(x/3, cnt+1);
            if(iscontinue){
                vecA.pop_back();
                visited[p2.second] = 0;
            }else return;
           
        }
    }
    
    if(iscontinue==false) return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){			//주어진 수열 B에서 하나씩 x로 지정해서 DFS 돌림
        visited[i] = 1;
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        if(iscontinue==true){					//수열 A 찾지 못했을 경우 pop 하고 다음 요소를 x로 지정해서 반복
            vecA.pop_back();
            visited[i] = 0;
        }else break;
    }
    
    return 0;
}

아래의 방법은 velog.io/@hschoi1104/BOJ-16936-%EB%82%983%EA%B3%B12

를 참고해서 위의 코드를 수정한 것이다. 

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int N;


void DFS(long long x, int cnt){

    if(cnt==N){
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        exit(0);
    }
    

    if(x%3==0 && find(vecB.begin(), vecB.end(), x/3)!=vecB.end()){
        vecA.push_back(x/3);
        DFS(x/3, cnt+1);
        vecA.pop_back();
    }
    if(find(vecB.begin(), vecB.end(), 2*x)!=vecB.end()){
        vecA.push_back(2*x);
        DFS(2*x, cnt+1);
        vecA.pop_back();
    }
    return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){
       
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        vecA.pop_back();
            
    }
    
    return 0;
}

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

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

접근 방법

완전탐색 문제라 모든 경우의 수에 대해 DFS 로 풀었는데 시간 초과가 떴다.

문제의 조건에서 순서를 상관하지 않으므로 IIX = XII 이다. 이는 중복 조합으로 해결할 수 있다.

중복조합은 서로 다른 n개 중 k 개를 뽑는 경우인데, 여기서는 서로 다른 4개(I,V,X,L) 개 중 중복을 허용하고 순서 상관 없이 N개를 뽑는것이다.

DFS() 안의 반복문을 보자.

시작 값을 변화시킴으로써 중복 조합을 구현할 수 있다. i의 변화 값은 다음과 같다. (4개만 나타냄)

(앞에 -가 붙은 경우는 시작 값을 i=0으로 고정시켰을 경우에 나오는 경우이다. 시작 값을 변화시킴으로써 IIX = XII 처럼 같은 수를 나타내는 경우 한번만 카운트 할 수 있다.)

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

- 0 0 1 0

0 0 1 1

0 0 1 2

0 0 1 3

- 0 0 2 0

- 0 0 2 1

0 0 2 2

0 0 2 3

- 0 0 3 0

- 0 0 3 1

- 0 0 3 2

0 0 3 3

...

//
//  BF_BOJ16922_로마숫자만들기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

using namespace std;

#define I 1
#define V 5
#define X 10
#define L 50

int N;
int answer = 0;
int sum = 0;
bool visited[1001] = {0};
char cArr[4] = {'I','V','X','L'};
int iArr[4] = {1,5,10,50};

vector<int> sumVec;
vector<string> strVec;
string str = "";
void pickDFS(int toPick, int start, int s){
    
    
    if(toPick==0){
        if(visited[s]==false){
            answer++;
            visited[s]=true;
        }
        return;
    }
    
    for(int i = start; i<4; i++){				//시작점을 바꿔서 중복 조합 구현 가능
        pickDFS(toPick-1, i, s+iArr[i]);
    }
    
}


int main(){
    cin>>N;
    pickDFS(N, 0, 0);
    cout << answer;
    
    return 0;
}

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

문제

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

입력

첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.

출력

양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값을 출력한다.

접근 방법

X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다. 즉 최소 가격이기만 하면 추가로 더 구매할 수 있다는 것이다. (단 max(X,Y) 보다 많이 구매한다면 최소 가격이 될 수 없음)

양념, 후라이드 각각 구매하는 것 보다 반반을 두마리 구매하는게 더 싸며 X>Y 라고 가정해보자. 

그럼 아래의 1) ~ 2) 사이에서 반반으로 얼마만큼 구매하느냐에 따라 가격이 달라지며, 반복문을 돌면서 최소 가격을 구한다. 

1) Y마리는 반반으로 구매하고,  (X-Y) 마리는 후라이드 치킨 따로 구매.

2) X마리 전부 반반으로 구매

//
//  BF_BOJ16917_양념반후라이드반.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다.
//즉, X,Y 개 이상 구입할 수 있는 것이다.
//반복문을 돌면서 반반으로 얼마나 구매해야하는지와 그때의 최소 가격을 구한다.

#include <iostream>
using namespace std;

int main(){

    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;
    
    
    bool ischeapBanBan = A+B>2*C ? true : false;    //양념 + 후라이드 각각 사는게 더 싼지 체크
    
    long long mini = 10000000000, sum;
    if(ischeapBanBan){
        
        if(X>Y) {
           
            for(int i = Y; i<=X; i++){
                sum = 2*C*i + (X-i)*A;          //(X-i) : 반반 구매하고 더 구매해야 하는 양념 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        else {
            for(int i = X; i<=Y; i++){
                sum = 2*C*i + (Y-i)*B;         //(Y-i) : 반반 구매하고 더 구매해야 하는 후라이드 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        
    }
    else{
        mini  = A*X + B*Y;
    }
    
    cout << mini;
    return 0;
}

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

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

접근 방법

완전탐색 문제로 모든 경우의 수를 다 구해주면 된다.

형식을 string 으로 입력받고, 첫 글자 type[0]에 따라 answer 값 초기 설정을 해준다. 

그 후 type[1] 부터 반복문을 돌면서 이전 형식과 일치하는지(연속하는지) 검사하면서 경우의 수를 곱해나간다. 연속하는 경우는 문자일 경우 26-1개를 곱하고, 숫자일 경우 10-1개를 곱한다. 

//
//  BF_BOJ16968_차량번호판1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//완전탐색
//이전과 형식 연속되는지만 체크해서 연속되면 해당 글자와 겹치지 않게 1 감소시켜서 곱하기


#include <iostream>
#include <string>

using namespace std;


int main(){
    
    string type;
    cin >> type;
    int answer;
    
    int numD = 10;      //0~9
    int numC = 26;      //a~z
    
    if(type[0]=='c') answer = numC;
    else answer = numD;
    
    for(int i = 1; i<type.length(); i++){       //이전 형식과 연속되는지 검사
        
        if(type[i]=='c'){
            
            if(type[i-1]=='c'){ //연속된 경우 cc
                answer *= (numC-1);
            }
            else{   //dc
                answer *= numC;
            }
        }
            
        else{
            
            if(type[i-1]=='c'){ //cd
                answer *= numD;
            }
            else{   //연속된 경우 dd
                answer *= (numD-1);
            }
        }
        
    }
    
    cout << answer;
    
    
    
    
    return 0;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42862#

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

접근 방법

매번 DFS를 돌 때마다 체육수업을 못 받는 학생 수를 카운트 해서 완전탐색으로 풀었다.

주의해야할 점은 제한사항 5번인데, 여분 체육복이 있고 도난당하지 않은 학생들의 번호만 vec에 넣어서 해결할 수 있었다.

처음에는  

DFS(int n, int toPick) 으로 파라미터를 하나 더 추가하고,

조건식을 하나 없애서 if(next<1 || next>n)  로 수정하고,

toPick 이 0이 될때 체육수업을 못 받는 학생 수를 카운트 하는 방식으로 했는데 이상하게 7번 테스트 케이스에서만 통과가 안 됐다. '질문하기'에서 나온 테스트케이스를 모두 넣어서 테스트 할 때는 통과 됐지만 제출하기를 누르면 통과가 되지 않았다. 

DFS 호출 전에 main 에서 이미 제한사항 5번을 처리해줬는데 어떤 부분이 문제인지 잘 모르겠다. 

//
//  DFS_프로그래머스_체육복.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <string>
#include <vector>

using namespace std;
vector<int> vec;
int arr[31];
int d[2] = {1, -1};
int visited[31] = {0};
int mini = 100;
void DFS(int n){

    int cnt = 0;
        for(int i = 1; i<=n; i++){
            if(arr[i]==0) cnt++;
        }
        if(cnt<mini) mini = cnt;
        
    for(int i = 0; i<vec.size(); i++){
        for(int j = 0; j<2; j++){
            int next = vec[i] + d[j];
            if(next<1 || next>n || arr[next]!=0) continue;      //범위 넘어가거나 옆사람 줄 필요 없으면
            
            if(visited[vec[i]]==0){
                visited[vec[i]] = 1;
                arr[vec[i]] -= 1;
                arr[next] += 1;
                DFS(n);
                arr[next] -= 1;
                arr[vec[i]] += 1;
                visited[vec[i]] = 0;
            }
            
        }
    }
}


int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int cnt=0;
    for(int i = 0; i<=31; i++){
        arr[i] = 1;
    }
    for(int i = 0; i<lost.size(); i++){ arr[lost[i]] -= 1;}             //안 가져온 사람
    for(int i = 0; i<reserve.size(); i++){ arr[reserve[i]] += 1;}       //여분 가져온 사람
    
    for(int i = 1; i<=n; i++){
        if(arr[i]==2) vec.push_back(i); //여분 체육복 갖고 온 사람이 도둑 맞은 경우는 arr[i] = 1이므로 arr[i] = 2인 경우만 인덱스 push
    }
    
    DFS(n);
    answer = n-mini;

    
    return answer;
}