백준 1107 - 리모컨 [C/C++]

1107번: 리모컨 (acmicpc.net)

1107번: 리모컨

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 우선 간단히 생각해보자.

 

• 리모콘의 특정 숫자버튼이 고장난거니깐, 우선 타겟 지점에서 가장 가까운, 고장 나지 않은 숫자들의 조합으로 표현될 때까지 위 아래로 가본다.
• 고장 나지 않은 숫자들의 조합으로 등장한 첫 번째 수와 타겟 까지의 차이가 바로 + 혹은 - 버튼을 누른 횟수일 것이다.
• 그 숫자 + 고장 나지 않은 숫자들을 누른 횟수가 최소값일 것이다.
• 고장 난 키가 없다면, 그 키를 누른 횟수와 100-타겟 중 최소값이 정답일 것이다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
int future, howmuchOut, dap;
string s;
char err[10];
bool isPossible[1000001];
int up = 0;
int down = 0;
int ans, result;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> future;
    cin >> howmuchOut;
    if (howmuchOut==0){
        int j = to_string(future).length();
        cout << min(abs(future-100), j);
        return 0;
    }
    for (int i=0;i<howmuchOut;i++){
        cin >> err[i];
    }
    for (int i=0;i<=1000000;i++){
        bool check = false;
        string k = to_string(i);
        int len = k.length();
        for (int j=0;j<len;j++){
            for (int w=0;w<howmuchOut;w++){
                if (k[j] == err[w]){isPossible[i]=false; check=true;break;}
            }
        }
        if (!check) isPossible[i] = true;
    }
    isPossible[100] = true;
    int downnum = future;
    int ch = 0;
    while (!isPossible[downnum]) {
        if (downnum==0) {
            if (future!=0) ch=1;
            break;
        }
        downnum--;
    }
    int leng = to_string(downnum).length();
    down = min(abs(future-100), future-downnum+leng);
    if (ch==1) down = abs(future-100);

    int upnum = future;
    while (!isPossible[upnum]) {
        upnum++;
    }
    int leng2 = to_string(upnum).length();
    up = min(abs(future-100), upnum-future+leng2);

    ans = (future!=0) ? min(up, down) : up;
    cout << ans;

    return 0;
}

 

• 먼저 아래로 내려가면서 isPossible이 True일 때까지 내려간다.
• (타겟 - 그 수 + 그 수를 리모콘으로 누르는데 필요한 횟수) 와 (100 - 그 수)의 절댓값 중 최소값이 down에 들어간다.
• 위로 올라가는 것도 마찬가지로 반복한다.
• 둘 중 최소값이 답이 될 것이다!