[C++] 백준 1107: 리모컨

문제 이해

- 리모컨 버튼은 숫자 0~9, +, -가 존재한다.

- +버튼을 누르면 현재 채널에서 +1된 채널로 이동한다.

- -버튼을 누르면 현재 채널에서 -1된 채널로 이동한다.

※단, 현재 채널이 0일때 -를 누를경우 변화는 없다.

- 채널은 무한대이며, N번으로 이동하고자 한다.

- N번으로 이동할 때 버튼을 누르는 횟수의 최솟값을 구하라.

- 현재 채널은 100이다.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 256MB

 

<입력>

- N: 이동하려는 채널(0 ~ 500,000, 10^5)

- M: 고장난 버튼의 개수 (0 ~ 10)

 

<출력>

- N번으로 이동하기 위해 눌러야하는 버튼의 최솟값을 구하라.

 

 

 

---

문제 풀이

처음엔 수학적으로 접근해서 

이것저것 경우의 수를 생각해봤는데 고려해야할 게 너무 많았다.

 

 

결국 인터넷 풀이를 참고하였는데

이 문제의 핵심은 n의 범위이다.

 

 

n의 최댓값은 500,000으로 

채널이 무한대여도 그 범위가 한정되어있다.

1,000,000까지만 가능성을 고려해줘도 괜찮다는 뜻이다!

 

 

그래서 두 가지 케이스로 구분하여 문제를 푸는데

1. 숫자 버튼을 누르지 않는 경우

2. 숫자 버튼을 누르는 경우

 

위의 두 가지이다.

 

 

1번은 n에서 100을 뺀 절댓값으로 구할 수 있고

int mymin = abs(numN-100);

 

 

2번은 0 ~ 1,000,000까지의 숫자가 가능한지 불가능한지 체크한 뒤,

 

그 숫자에서부터 n까지 '+ or -버튼으로 이동하는 데 드는 횟수' + '숫자 버튼을 누른 횟수'로 구해줄 수 있다.

for(int i = 0; i <= 1010101; i++){
    if(check(i)){
        int tmp = abs(numN-i) + to_string(i).size();
        mymin = min(mymin, tmp);
    }
}

 

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

bool num[10];

bool check(int now){
    string s = to_string(now);
    for(int i = 0; i < s.size(); i++){
        if(num[s[i] - '0'] == false) return false;
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int i = 0; i < 10; i++) num[i] = true;

    string n;
    int m;
    cin>>n>>m;
    while(m--){
        int tmp;
        cin>>tmp;
        num[tmp] = false;
    }

    int now = 100;
    int numN = stoi(n);

    int mymin = abs(numN-100);

    for(int i = 0; i <= 1010101; i++){
        if(check(i)){
            int tmp = abs(numN-i) + to_string(i).size();
            mymin = min(mymin, tmp);
        }
    }

    cout<<mymin;
    return 0;
}

 

 

 

---

배운 점

n의 범위를 보고 O(n) 풀이를 먼저 생각해봤어야 될 거 같은데, 전혀 고려하지 못했다.

될 수 있는 모든 경우의 수의 값들을 비교하는 것도 고려하도록 하자.