[C/C++] BOJ 1107 :: 리모컨

BOJ 1107 :: 리모컨

문제 링크 : https://www.acmicpc.net/problem/1107

처음에는 수학적으로 접근하였다.

이동하려는 채널을 누를 수 없을 때,

같은 자리 수,

가장 가까운 작은 수 만들기.

가장 가까운 큰 수 만들기.

한 자리 작은 수,

제일 큰 수 만들기.

한 자리 큰 수.

제일 작은 수 만들기.

이동한 채널에서 (+)/(-)를 눌러 채널에 도착한 후, ans 갱신

ans와 이동하려는 채널에서 현재 채널(100)을 뺀 값 비교 후 갱신.

그런데 이렇게 다 분할하여 짜려고 하다보니 코드가 지저분해지고,. 반례들이 무궁무진하게 나오면서.. 굉장히 어려웠다 ㅠㅠ

그래서 다시 refresh해서 그냥 모든 채널을 이동하는 방식으로 코드를 수정하였다. ... 완전히 엎어버렸다능

백준 질문게시판에 있는 게시물의 Test case로 잘못된 점을 찾아가며 풀 수 있었습니다..!...// 너무너무 고마우신 분 ㅠㅠ

리모컨 반례 : https://www.acmicpc.net/board/view/31853

나의 풀이

1) 시작채널과 목적채널이 같으면 0을 출력하고 return

2) 모든 숫자를 누를 수 있으면 숫자를 눌러 이동하고 ans 갱신

3) 0만 누를 수 있으면 0을 누른 후 목적 채널로 이동하고 ans 갱신

4) 모든 채널을 누르면서 비교 ans 갱신

- 모든 채널이라고는 하였으나 최소 이동 횟수를 구하기 위해서는

목적 채널 자리 수 -1과 목적 채널 자리 수 +1 사이에서만 채널을 이동하면 되기 때문에 이 부분을 고려하여 처리해 주었다.

( 2), 3), 4)는 (+) 나 (-) 버튼을 눌러 이동한 것과 비교해야 하기 때문에 출력하고 return 하면 안된다.)

5) (+) / (-) 버튼을 눌러 목적 채널을 이동한 값과 ans 비교 갱신 후 출력

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1107/BOJ_1107.cpp

// 백준알고리즘 1107 :: 리모컨
#include<iostream>
#include<string>
using namespace std;
int N;
int dest;
int len_dest;
int start = 100;
int ans = 1000000;
int num[7] = { 0 };
int disnum[10];
 
// pos : 몇 자리 수인지
int arrtonum(int pos)
{
    int ret = 0;
    for (int i = 0; i < pos; i++)
        ret = ret*10 + num[i];
    return ret;
}
 
// p자리까지 채워야 한다.
// idx 자리를 채워야 할 차례이다.
void fillnum(int p, int idx)
{
    // p자리까지 채웠다.ans 갱신
    if (idx == p)
    {
        int n = arrtonum(p);
        int lans = abs(dest - n)+p;
        if (ans > lans)    ans = lans;
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {
        if (disnum[i]) continue;
        num[idx] = i;
        fillnum(p, idx+1);
        // 이 구문을 넣었을 때가 오히려 4ms가 절약된다. 왜지..?
        num[idx] = 0;
    }
    return;
}
 
int main(void)
{
    string str;
    cin >> str;
    len_dest = str.length();
    dest = stoi(str);
 
    cin >> N;
    int data = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> data;
        disnum[data] = 1;
    }
 
    // 시작과 목적 채널이 같다.
    if (dest == 100) {
        cout << 0;
        return 0;
    }
    // 모든 숫자 버튼을 다 누를 수 있다. => 숫자 버튼으로 목적 채널을 누르는 것과 (+) / (-) 로 현재 채널에서 이동하는 것을 비교
    else if (N == 0) ans = len_dest;
    // 0만 누를 수 있다. => 0을 누르고 목적 채널로 이동하는 것과 (+) / (-) 로 현재 채널에서 이동하는 것을 비교
    else if (disnum[0] == 0 && N == 9) ans = 1 + dest;
    else
    {
        int idx = 0;
 
        // 0을 눌렀을 때
        if (disnum[0] == 0) ans = dest + 1;
 
        // 자릿수가 목적 채널보다 1 작은 채널부터 시작한다.
        int l = len_dest;
        if (l == 1) l = 2;
 
        // 1자리에서 7자리까지 채우기
        // 맨 앞은 0을 넣을 수 없다.
        for (int p = l-1; p < 8; p++)
        {
            // 자릿수가 목적 채널보다 2개 많은 채널로 이동할 필요가 없다.
            if (len_dest < p-1) break;
            for (int i = 1; i < 10; i++)
            {
                // 이 구문을 넣었을 때, 약 20ms가 절약되었다.
                if (disnum[i])continue;
 
                num[idx] = i;
 
                // 한 자리만 채우면 된다.
                if (p == 1)
                {
                    int n = arrtonum(p);
                    int lans = abs(dest - n)+p;
                    if (ans > lans) ans = lans;
                    continue;
                }
                fillnum(p, idx+1);
            }
        }
    }
 
    // ans와 (+) / (-) 로 현재 채널에서 이동하는 것을 비교한다.
    int movechannel = abs(dest - start);
 
    if (ans > movechannel) ans = movechannel;
 
    cout << ans;
    
    return 0;
}