[Baekjoon] 1107 - 리모컨 (C++)

1. 문제

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장 난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

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

1107번: 리모컨

---

2. 해결 아이디어 / 참고 알고리즘

처음엔 따로 특정 알고리즘이 있나 곰곰이 생각했지만, 너무 복잡하게 생각할 필요 없이 일단 Brute Force부터 생각해도 버튼의 개수도 적고 채널 수도 그렇게 많지 않아 brute force로 풀어도 시간 초과가 뜨지 않는 문제이다.

 

어떤 채널의 번호를 입력받으면, 그 채널의 번호를 현재 누를 수 있는 버튼의 조합으로 만들 수 있는지를 판별하는 함수를 따로 만들어 목표 번호에서 가장 가까운 '한 번에 갈 수 있는 번호'를 찾으려고 했다.

 

일단 먼저 현재 번호(100)에서 하나씩 증가/감소시키며 목표 채널까지 가는데 걸리는 횟수를 minCnt에 저장했고, 그다음에 목표 채널보다 낮을 때/높을 때 갈 수 있는 가장 가까운 번호로 가는 횟수 + 목표 채널까지 1씩 증가/감소시키며 가는 횟수가 이보다 작은지 판별해줬다.

 

번호의 길이가 좀 더 길어지거나 처음 시작하는 번호가 다소 커진다면 까다로워질 수도 있는 문제인 것 같다.

---

3. 개선할 점

• 최근에 너무 특정 알고리즘 유형만 풀어 Brute Force로 푸는 법을 다소 잊어버린 듯하다. 일단 Brute Force로 풀 수 있는 가능성을 먼저 확인하고, 다음 알고리즘으로 넘어가는 습관을 기르자.

---

4. 코드

번호의 길이가 길어짐에 따라 번호를 검사하는 시간이 커지므로 시간 복잡도는 O(nlogn)으로 산정했다.

// Baekjoon No. 1107 리모컨 - 221001
// Time Complexity O(nlogn)
// # Brute Force

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#define SIZE 10
using namespace std;

int validate(int[SIZE], int);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string str;
    int n, m, minCnt, status, cmp;
    int i;
    cin >> n >> m;
    str = to_string(n);
    int buttonStatus[SIZE] = { 0 };
    for (i = 0; i < m; i++) {
        cin >> status;
        buttonStatus[status] = 1;   // 고장남 1
    }

    // solving
    minCnt = (100 > n) ? 100 - n : n - 100;
    if (minCnt > 0 && m < 10) {
        cmp = n;
        while (!validate(buttonStatus, cmp) && cmp > 0 && n - cmp + to_string(cmp).length() <= minCnt) cmp--;   // n�� length�� �ƴ� cmp�� length�� ���.
        if (n - cmp + to_string(cmp).length() < minCnt && validate(buttonStatus, cmp)) minCnt = n - cmp + to_string(cmp).length();
    }
    if(minCnt > 0 && m < 10) {
        cmp = n + 1;
        while (!validate(buttonStatus, cmp) && cmp - n + to_string(cmp).length() <= minCnt) cmp++;
        if (cmp - n + to_string(cmp).length() < minCnt && validate(buttonStatus, cmp)) minCnt = cmp - n + to_string(cmp).length();
    }

    cout << minCnt;

    return 0;
}
int validate(int buttonStatus[SIZE], int n) {
    string str = to_string(n);
    for (int i = 0; i < str.length(); i++) {
        if (buttonStatus[str[i] - '0'])
            return 0;
    }
    return 1;
}