[BOJ] 1107 리모컨

 

1107번: 리모컨

 

충격과 공포의 문제이다. 엄청 더럽게 if문 많이 해서 풀었는데 전혀 그런식으로 푸는 문제가 아니었다.

브루트 포스로 처음부터 끝까지 하나하나 확인하면서 가는 문제이다. 

 

반례↓

글 읽기 - [반례모음]

 

1555
8
0 1 3 4 5 6 7 9
670


10
9
1 2 3 4 5 6 7 8 9
11

0
9
1 2 3 4 5 6 7 8 9
1

100000
9
0 1 2 3 4 5 6 7 8
6

2229
6
4 5 6 7 8 9
5

10
1
0
2

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

9
8
0 3 4 5 6 7 8 9
4
-> 11인 경우로 시작해야 한다.

-> 자릿수마다 확인하는 것 안된다.

 

0
3
0 1 2
4
-> 0 인 경우 log값 안나온다. 

---

 

 

생각보다 간단한 알고리즘인데, 문제에서 주어진 최대 범위는 5000000이지만, 그 위에서 내려가는 경우를 생각해야 하기 때문에 실제적으로 범위는 1000000까지 잡아줘야 해요

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

using namespace std;


vector<int> dp;
vector<bool> mal(10,false);

bool check(int now){

    string s = to_string(now);
    for(int i = 0; i <s.length();i++){
        if(mal[s[i]-48]){
            return false;
        }

    }

    return true;

}



int main(){

    int n,c;
    cin>>n>>c;

    int tmp;

    for(int i = 0; i < c; i++){
        cin>>tmp;
        mal[tmp] = true;
    }


    string st = to_string(n);

    int minimum = abs(n-100);
    for(int i = 0; i <= 1000000; i++){
        if(check(i)){
            int tmp = abs(n-i)+to_string(i).length();
            minimum = min(minimum,tmp);
        }

    }


    cout<<minimum<<endl;


    return 0;
}

 

 

 

 

[백준] 1107 리모컨 - C++ 문제풀이