[c++] BOJ 1107번 :: 리모컨 (코드, 테스트케이스)

리모컨

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	29717	6775	4628	22.196%

문제

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

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

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

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

입력

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

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

나의 답

코드

첫번째 (조건 사용)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, M;
int tmp_arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
vector<int> num_arr;
vector<int> clicked_btns;
vector<int>::iterator iter;

int near_num = 1e9;
int store_num = 1e9;
int length_N;

bool isInNumArr(int num) {
    int size = num_arr.size();
    for (int i = 0; i < size; i++) {
        if (num == num_arr[i])
            return true;
    }
    return false;
}

void findNearNum(int num, int len, int now_num) {
    if (len == -1) {
        int tmp = abs(N - now_num);
        if (near_num > tmp) {
            near_num = tmp;
            store_num = now_num;
        }
        return;
    }

    vector<int> tmp_buttons;
    if (length_N == len + 1 && len>0) 
        // 두 자리 이상일 때, 맨 처음에 0이 나올 수 있음
        // 100 이하일 떄 첫자리에 0이 나올 수 있으므로 1번만 check하면 됨
        // 100이상일 떄는 0이 나와도 100에서 이동하는 것이 더 나으므로 두 번 이상 비교할 필요 x
        tmp_buttons.push_back(0);

    int first = num / pow(10, len);

    /*
    if (first < 0)
        first = -1;
    else if (first > 10)
        first = 10;
    */

    int flag = 0;
    if (isInNumArr(first)) {
        tmp_buttons.push_back(first);
        flag = 1;
    }

    int dist = 1;
    while (1) { //3
        if (isInNumArr(first - dist)) {
            tmp_buttons.push_back(first - dist);
            flag = 1;
        }
        if (isInNumArr(first + dist)) {
            tmp_buttons.push_back(first + dist);
            flag = 1;
        }
        dist++;
        if (first - dist < 0 && first + dist > 9)
            break;
        if (flag)
            break;
        flag = 0;
    }

    int size = tmp_buttons.size();
    for (int i = 0; i < size; i++) { // 3
        int tmp = tmp_buttons[i];
        findNearNum(num - tmp * pow(10, len), len - 1, now_num * 10 + tmp); // 6
    }
}

int getLength(int num) { // 6
    int length = 1;
    while (num /= 10)
        length++;
    return length;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int tmp; cin >> tmp;
        tmp_arr[tmp] = -1;
    }

    for (int i = 0; i < 10; i++) { // 있는 버튼 저장
        if (tmp_arr[i] != -1)
            num_arr.push_back(i);
    }

    int n1 = abs(N - 100);

    length_N = getLength(N);
    findNearNum(N, length_N - 1, 0);

    int n2 = near_num + getLength(store_num);

    //cout << near_num << " " << store_num << endl;

    cout << (n1 > n2 ? n2 : n1);
}

 각 자릿수마다 가장 가까운 자리(최대 3개)를 arr에 넣고 재귀 호출해서 푸는 방식이다. 이 코드에서는 자릿수때문에 주어져야할 조건이 많은데, 이 조건을 다 기재하는 것보다 brute force 방법을 사용하는 것이 낫다.

 

ex_)

1000
2
0 1

일 때, 4자리 수가 아니라 3자리 수인 999를 고려하려면 첫자리에 0이 나올 수 있도록 하면 된다.

9999
1
9

일 때, 4자리 수가 아니라 5자리 수인 10000을 고려하려면 한 자리 수 더 큰 자릿수부터 계산하면 된다.

이렇게 복잡해지므로 brute force를 이용하는 것이 낫다.

 

 

두번째 (brute force)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, M;
int N_length = 0;
int tmp_arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
vector<int> num_arr;

int near_dist = 1e9;
int near_num = 1e9;

int getLength(int num) {
    int length = 1;
    while (num /= 10)
        length++;
    return length;
}

void findNearNum(int size, int num) { // size : 숫자 길이
    if (size == 0) {
        int tmp = abs(N - num) + getLength(num);
        if (tmp < near_dist) {
            near_dist = tmp;
            near_num = num;
        }
        return;
    }

    int num_size = num_arr.size();
    for (int i = 0; i < num_size; i++) {
        findNearNum(size - 1, num * 10 + num_arr[i]);
    }
}

int main() {
    cin >> N >> M;

    int tmpN = N;
    N_length = getLength(N);

    for (int i = 0; i < M; i++) {
        int tmp; cin >> tmp;
        tmp_arr[tmp] = -1;
    }

    for (int i = 0; i < 10; i++) { // 있는 버튼 저장
        if (tmp_arr[i] != -1)
            num_arr.push_back(i);
    }

    int n1 = abs(N - 100);
    int n2 = 1e9;

    if (num_arr.size() != 0) {
        for (int size = N_length - 1; size <= N_length + 1; size++) {
            if (size == 0) { // 한글자
                continue;
            }
            findNearNum(size,0);
        }
    }

    n2 = near_dist;
    //cout << near_dist << " " << near_num << endl;

    cout << (n1 > n2 ? n2 : n1);
}

 

 

테스트케이스

1235 3
1 2 3

=> 236 999
=> 239

0
9
0 1 2 3 4 5 6 7 9
=> 8 8
=> 9

5678
0
=> 0 5678
=> 4

150
2
1 6
=> 50 200
=> 50

9999
1
9
=> 10000
=> 6

(첫번째 코드에서 안되는 testcase)
=> 8888
=> 1115


1000
2
0 1
=> 999
=> 4

(첫번째 코드에서 안되는 testcase)
=> 2222
=> 900

=> 1 999
=> 4

199
1 9
=> 4

첫번째 코드가 실패한 이유는 주어진 수에서 자릿수가 하나 더 높은 경우나 하나 더 낮은 경우를 다룰 수 없기 때문이다. 조건을 많이 주면 할 수 있겠지만 brute force로 풀 수 있기 때문에 brute force를 이용하는 것이 좋겠다.