리모컨 #1107 c++ 풀이

 

https://www.acmicpc.net/problem/1107

1107번: 리모컨

브루트 포스 2초 2억번 계산에 맞게 알고리즘 짜기가 생각보다 만만치 않았던 문제

0. 0인 경우 0.
1. 처음부터 +,-로만 이동하는 경우와 비교
2. 어디까지 이동한 다음 + 혹은 -로 이동하는 경우와 비교

   2.1. 어디까지 이동이라는 것은 고장나지 않은 숫자로 만들수 있는 모든 숫자를 의미(brute force)

   2.2. 그런 다음 abs(이동한 수 - target)을 숫자에 더해줌
ans = min(1,2); //정답

 

모든 수를 구할때, MAX 를 가정하는 것이 어려웠다. 
//예제입력 3에서 500000으로 가는 경우 1,5을 제외한 모든 숫자가 고장남
//11117이 나오려면, 511111(6번) -를 11111번 눌러야함

// MAX가 500000라면, 34~~~~ 의 수가 나옴 예제 정답은 1111~~
// MAX가 500000보단 크다는 결론.
// 999999 0-9로 만들수 있는 가장 큰 수가 MAX일 것.

 

따라서 10만 * log(50만) 정도의 연산으로 해결

24ms => 1초 : 10^8 = 0.024초 : x ,

x  = 24*10^5번 계산

#include <iostream>
#include <string>
#include <cmath> 
#define MAX 999999
//0. 0인 경우 0.
//1. 처음부터 +,-로만 이동하는 경우와 비교
//2. 어디까지 이동한 다음 + 혹은 -로 이동하는 경우와 비교
//ans = min(1,2);

//예제입력 3에서 500000으로 가는 경우 1,5을 제외한 모든 숫자가 고장남
//11117이 나오려면, 511111(6번) -를 11111번 눌러야함
// MAX가 500000보단 크다는 결론.
// 999999 0-9로 만들수 있는 가장 큰 수가 MAX일 것.

using namespace std;

int n;
bool state[10];


bool check(int num) {
    if (num == 0) {
        if (state[0] == false) return false;
        else return true;
    }
    while (num) {
        if (state[num % 10] == false) return false;
        num /= 10;
    }
    return true;
}


int getMin(int num)
{
    int minPressCnt = MAX, pressCnt;
    for (int i = 0; i <= MAX; i++) {
        if (check(i)) {
            pressCnt = to_string(i).length();
            pressCnt += abs(i - num);
            minPressCnt = min(minPressCnt, pressCnt);
        }
    }
    return min(abs(num - 100), minPressCnt);
}

int main(void)
{
    int m, tmp;
    cin >> n >> m;
    for (int i = 0; i < 10; i++) state[i] = true; // init
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        state[tmp] = false;
    }
    cout << getMin(n) << '\n';
    return 0;
}