개발 블로그

문제 링크 :  https://www.acmicpc.net/problem/1107

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

접근 방법

간단해 보이지만 의외로 복잡한 문제였다.

누군가 친절하게 올려주신 반례를 사용해서 풀 수 있었다.

* 반례 모음(https://www.acmicpc.net/board/view/46120)

1555
8
0 1 3 4 5 6 7 9

를 예로 들어보자. 결론부터 말하면 답은 670이고 888을 누른 뒤(3번) 667번(1555-888) -버튼을 누를 때가 최소로 버튼을 눌러서 1555를 만드는 경우이다. 나는 아래의 방법으로 생각해서 틀렸다. 

처음에는 한 자리수씩 따져서 고장나지 않은 버튼으로 누를 수 있는 숫자를 만든 후 더 적게 +/-를 눌러서 N에 도달하는 경우일 때 해당 숫자를 저장했다.

즉, 1은 고장난 버튼이니 

case1) 2부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 2

case2) 0부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 없음

2를 저장한다.

그 다음은 5인데, 5도 고장난 버튼이니

case1) 6부터 9까지의 수 중에 고장나지 않은 버튼 중 최소 수를 구한다. -> 8 -> 28 -15 = 13

case2) 4부터 0까지 수 중에 고장나지 않은 버튼 중 최대 수를 구한다. -> 2 -> 22 - 15 = 7

13>7로 더 작은 case2) 의 2를 앞에서 저장한 2 뒤에 붙여 22를 저장한다. 

그래서 결국 2222를 만든 후(2버튼 4번 누름) 667번(2222-1555)을 -버튼을 눌러서 1555를 만들 수 있다. 이 때 답은 4+667 = 671이 된다. 

결국 완전 탐색으로 풀어주었다. i = 0부터 999999까지 돌면서 (N의 최대값이 500,000이므로 6자리수 중 최대 값까지 검사한다) 검사한다.

만약 고장난 버튼 때문에 i를 바로 누르지 못하면 다음 수를 검사한다.

아니라면 i의 자리수 + |N-i| 를 구하며 이 값의 최소값을 저장한다.

import java.util.*;

public class BF_BOJ1107_리모컨 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int N, M;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		ArrayList<Integer> troubleButton = new ArrayList<Integer>();
		
		
		for(int i = 0; i<M; i++) {	//고장난 버튼 
			int but = sc.nextInt();
			troubleButton.add(but);
		
		}
		
		int ans = Math.abs(100-N);			//+, - 버튼으로만 움직였을 때 
		
		int mini = 987654321;
		int cnt = 0;
		
		for(int i = 0; i<=999999; i++) {		//완전 탐색 
			
			String str = String.valueOf(i);
			boolean chk = true;
			for(int k = 0; k<str.length(); k++) {
				if(troubleButton.contains(str.charAt(k)-'0')) {		//고장난 버튼 때문에 바로 i 못 누르면 스킵 
					chk=false; break;
				}
			}
			if(chk==false) continue;
			
			cnt = str.length() + Math.abs(i-N);	//고장난 버튼 없어서 바로 i를 누를 수 있으면 i 누르고 +/- 눌러서 이동  
			
			
			if(cnt < mini) {
				mini = cnt;
			}
	
		}
		
		if(mini < ans) ans = mini;
		System.out.println(ans);

		
	}

}

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

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

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

접근 방법

재귀를 이용해서 풀었다. DFS와 같은 구조이다. 

9명 중 7명을 뽑아서 toPick이 0이 되었을 때 키를 모두 더해서 키의 합이 100이면 chk를 true로 바꾸서 탐색을 멈췄다.

문제에서 조건을 만족하는 경우 중 아무거나 출력하라 했으니 sum=100이 되는 경우를 찾았을 때 진행을 멈추는 것이 효과적일 것이다.

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

using namespace std;


vector<int> heightVec;
bool isVisited[9] = {0};
bool chk = false;
vector<int> ansVec;
int ans = 0;

void Func(int sum, int toPick){
    
    if(toPick==0){
        
        if(sum==100){
            chk = true;
            return;
        }
  
    }
    
    for(int i = 0; i<9; i++){
        
        if(isVisited[i]==0){
            isVisited[i] = 1;
            ansVec.push_back(heightVec[i]);
            sum+=heightVec[i];
        
            Func(sum, toPick-1);
            if(chk){ break;}
            
            sum-=heightVec[i];
            ansVec.pop_back();
            isVisited[i] = 0;
        }
        
    }
    
}


int main(){
    
    
    for(int i = 0; i<9; i++){
        int h;
        cin>>h;
        heightVec.push_back(h);
    }
    
    sort(heightVec.begin(), heightVec.end());
    
    Func(0, 7);
    
    for(int i = 0; i<7; i++){
        cout << ansVec[i] << "\n";
    }
    
    
    return 0;
}