C++ 백준 1107 리모컨

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

1107번: 리모컨

 

문제를 보고 어떤식으로 풀어야할지 감이 잘 오지 않아서 공부할겸 포스팅하게 되었습니다.

 

문제풀이

처음에는 "각 자리수별로 조각을 내어 재귀 호출하여, n과 같아질 때까지 모든 경우의 수를 탐색하면 어떨까?" 라고 생각했지만 코드를 어떻게 작성해야할지 막막했다.

 

문제를 다시 읽고 문제가 시키는대로 따라가야겠다고 생각하고 가능한 경우를 추상화하여 정리를 해보니 

1. +/-로 모두 이동하는 경우

2. 가장 가까운 수로 이동한 후 +/-로 이동하는 경우

3. 한 번에 이동하는 경우

 

세 가지로 정리할 수 있었고, 하나씩 구현을 하면 되겠다고 생각하여 풀이를 시작하였다.

풀다보니 2번과 3번은 한 번에 해결할 수 있었다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int brokenCnt;
bool isBroken[11];
int ans;

bool hasBrokenNum(const string& s) {
    bool check = false;
    for (const auto &c: s) {
        if(isBroken[c-'0']) { // 현재 숫자에서 고장난 채널이 있으면
            check = true;
        }
    }
    return check;
}

void solve() {
    for(int i=n; i>=0; i--) { // 아래로 가장 가까운 수 찾기
        string s = to_string(i); // 숫자 길이를 활용하기 위해 문자열로 변환
        if(!hasBrokenNum(s)) {
            int tmp = s.size() + (n-i); // 숫자의 길이만큼 채널을 누르고, 나머지 차이만큼 +또는 -버튼
            ans = min(ans, tmp);
            break;
        }
    }
    for(int i=n; i<=n+ans; i++) { // 위로 가장 가까운 수 찾기
        string s = to_string(i);
        if(!hasBrokenNum(s)) {
            int tmp = s.size() + (i-n);
            ans = min(ans, tmp);
            break;
        }
    }
}

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

    cin >> n >> brokenCnt;
    for(int i=0; i<brokenCnt; i++) {
        int x;
        cin >> x;
        isBroken[x] = true;
    }
    ans = abs(n-100); // +/-로만 이동하는 경우
    solve();
    cout << ans;
}

위로 가장 가까운 수를 찾을 때 i<=n+ans만큼 하였는데, 이때 ans는 +/-로만 이동하는 경우 누르는 버튼의 수이므로 n+ans를 상한으로 설정하였다.