(C++) - 백준(BOJ) 1107번 : 리모컨 답

www.acmicpc.net/problem/1107

1107번: 리모컨

backtracking으로 푸는 문제였습니다.

 

풀이방법

 1. 고장나지 않은 channel 번호를 vector 배열에 저장합니다.

 2. 모든 자리 수에 대해(1자리~7자리) 고장나지 않은 channel번호를 backtracking으로 대입하여 목표 channel에서 가장 가까운 channel을 구합니다.

 3. 100번으로 시작해서 목표 channel로 가는 것과 backtracking하여 구해낸 답 중 적은 수를 출력합니다.

 

Code

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

int channelToGo;
int brokenNum;
int result = 0x7f7f7f7f;

int brokenChannels[10];
vector <int> nonBrokenChannels;

void getNumberToPush(int cnt, int value, int num){
    if(cnt==num){
        result = min(result, abs(channelToGo - value) + num);
        return;
    }
    for(int i =0; i < nonBrokenChannels.size(); i++){
        getNumberToPush(cnt+1, value*10+nonBrokenChannels[i], num);
    }   
}

int main(){
    cin >> channelToGo >> brokenNum;

    for(int i = 0; i < brokenNum; i++){
        int channelNum;
        cin >> channelNum;
        brokenChannels[channelNum] = 1;
    }

    for(int i = 0; i< 10; i++){
        if(!brokenChannels[i])
            nonBrokenChannels.push_back(i);
    }

    for(int i = 1; i <= 7; i++)
        getNumberToPush(0,0,i);
    cout << min(abs(100-channelToGo),result); 
}

 

Test Case

질문란에 있는 반례모음을 참고한 후 제가 만든 몇가지 테스트 케이스를 추가했습니다.

 

Input

1555
8
0 1 3 4 5 6 7 9

Output : 670

 

Input  

101
3
4 5 6

Output : 1

 

Input
162
9
0 1 3 4 5 6 7 8 9
Output : 62

 

Input  
10
9
1 2 3 4 5 6 7 8 9
Output : 11

 

Input   
1
10
0 1 2 3 4 5 6 7 8 9  
Output : 99

 

Input
1
1
1
Output :  2

 

Input
0
9
1 2 3 4 5 6 7 8 9
Output : 1

 

Input
101
0
Output : 1

Input
100000
9
0 1 2 3 4 5 6 7 8
Output : 6

 

Input
1
10
0 1 2 3 4 5 6 7 8 9
Output : 99

 

Input
1111
9
1 2 3 4 5 6 7 8 9 
Output : 1011

 

Input
2229
6
4 5 6 7 8 9
Output : 5

 

Input  
10
1
0
Output : 2

 

Input    
0
10
0 1 2 3 4 5 6 7 8 9
Output : 100

 

Input   
9
8
0 3 4 5 6 7 8 9
Output : 4

 

Input   
0
3
0 1 2
Output : 4

 

Input

104

0

Output : 3

 

Input

999

8

2 3 4 5 6 7 8 9

Output : 5