[브루트포스] 백준 1107번 리모컨(C++)

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

 

와우

 

수빈이 손꾸락 힘이 얼마나 쎈거야

 

버튼을 너무 세게 눌른 수빈이

mz답게 버튼 누르는 수빈이를 지브리풍으로 그려달라해봄..

공감성 능력까지 좋은 우리 지피티..

 

 

진짜 이 문제 너무 오래걸렸어요

 

먼저 문제에 대한 설명을 예시를 들면서 하겠습니다.

 

수빈이가 5500이란 숫자로 이동하고 싶으면

 

5 / 5 / 0 / 0 

이렇게 4번을 누르면 됩니다

 

근데 만약에 0번이란 숫자가 고장나 있을 경우

 

5 / 5 / 1 / 1 

번이란 숫자에 가서

-를 11번 해주거나

 

5 / 4 / 9 / 9 

에 가서

+를 한번해주면 되겠죠?

 

"총 리모컨 버튼을 누른 횟수"

-위에 해당하는것은 12(플러스 마이너스) + 4(5 5 1 1)

-아래에 해당하는 것은 1(플러스 마이너스 ) + 4 ( 5 4 9 9)

번이겠죠

 

그래서 아마 최솟값은 5일겁니다.

 

아래의 과정은 틀린 답을 유추하는 과정입니다 ^^ 안읽어도 됩니다..

 

이문제를 풀면서 제가 아직 몽매한 아지랑이 라는걸 깨닫습니다.

앞선 나의 과오를 먼저 보여주겠다.

 

#include <iostream>

#include <string>

#include <cmath>

#include <algorithm>

#include <cstdlib>

using namespace std;

int main()

{

    int c = 100;

    string tc;

    cin >> tc;

    int len = tc.length();

    // cout << len << " : 길이 \n";

    int n;

    cin >> n;

    int arr[n];

    int result[len];

    int sol = 0;

    int target = 0;

    for (int i = 0; i < n; i++)

        cin >> arr[i];

    cout << len << "<<len\n";

    for (int i = 0; i < len; i++)

    {

        int temp = tc[i] - '0';

        cout << temp << " << temp \n";

        int temp_1 = temp, temp_2 = temp;

        int sig = 1;

        int pr_t1 = temp, pr_t2 = temp;

        for (int j = 0; j < n; j++)

        {

            if (temp_1 == arr[j])

            {

                sig = 0;

                if (temp_1 != 9)

                    temp_1 += 1;

                else

                {

                    temp_1 = 9999999;

                }

            }

            if (temp_2 == arr[n - j - 1])

            {

                sig = 0;

                if (temp_2 != 0)

                    temp_2 -= 1;

                else

                    temp_2 = -9999999;

            }

        }

        if (sig == 1)

            result[i] = temp;

        else

        {

            if (temp_1 - temp > temp - temp_2)

                result[i] = temp_2;

            else

                result[i] = temp_1;

            // cout << "temp_1 : " << temp_1 << ", temp_2 : " << temp_2 << ", temp : " << temp << ", result[" << i << "] : " << result[i] << "\n";

        }

        sol += result[i] * pow(10, len - i - 1);

        target += temp * pow(10, len - i - 1);

    }

    cout << min(abs(target - 100), abs(target - sol)+len);

}

코드는 이해 안해도 된다

 

제가 먼저 생각한 것은

 

* 잘못된 풀이 *

1. 앗 그렇다면 가장 가까운 번호로 가서

2. 플러스 마이너스 해주면 되겠네?

 

해가지고 가장 가까운 번호를 가는데, 

사실 이게 경우의 수가 엄청 많고 따로 조건문을 해주는 것도 코드가 굉장히 길어지며 사실상 불가능합니다.

 

근데 저는 귀신에 홀린건지 

"아하 특정 i번째 숫자에 대해서 가장 가까운 숫자를 찾아주고! (ex : 4일때 금지숫자가 3 4 5 6 일 경우 가장 가까운 숫자는 2) 플러스 마이너스를 하면 되겠네!"

 

라고 해서 푼 문젠데..

딱봐도 식도 복잡하고 뭐..

저렇게 하면 10000에 대해서 1이 금지되어있으면 9999에서 1더하는게 더 빠른데 

뭐 가장 가까운 숫자인 2로 들어가서 10000번 더해주는 불상사를 겪은 것...

 

한 두시간 넘게 끙끙대며 풀었는데 정녕 답이 안나오고 후반엔 알고리즘 자체가 잘못되었다는 것을 알고 절망한 상태로 인터넷 검색을해서 알고리즘을 보고 내 코드대로 다시한번 풀었다.

 

내가 찾은 알고리즘은 훨씬 간단했다

 

방금 위에서 내가 유추한 식에서 말했다 시피 가장 가까운 번호를 찾는것은 조건도 많아지고 힘들다그렇다면?

 

"모든 경우의 수를 보자"이래서 브루트 포스 문제였던 것임...

 

그렇다면 들어갈 수 있는 숫자는 500000 (오십만)이므로 6숫자임 대략 백만까지는 사용자가 숫자를 임의로 넣을 수 있음(예를들어 999,999 에서 찾아갈 수 있잖아, 사용자가 최대 50만 채널까지 찾는다 해도 저기서 새롭게 찾아갈 수 있음)

 

그럼 이제 남는 것은

 

1.i=0부터 1,000,000까지 금지된 숫자가 들어가는지 확인하고2. 횟수를 구해낸다. ( 횟수를 구해내는 것은 단순히 마이너스를 해주면 됨 / 왜냐? 505번에서 500번으로 갈때 빼주면 5번 움직이는거잖아)3.min 함수를 사용해서 최솟값을 계속 갱신4.맨 마지막 출력 전 100에서 타겟값을 뺀 절댓값과 최솟값 비교

 

#include <iostream>

#include <string>

#include <cmath>

#include <algorithm>

#include <cstdlib>

using namespace std;

int main()

{

    int c = 100;

    string tc;

    cin >> tc;

    int len = tc.length();

    int n;

    cin >> n;

    int arr[n];

    int result[len];

    int sol = 0;

    int target = 0;

    for (int i = 0; i < n; i++)

        cin >> arr[i];

    int temp_min = 9999999;

    for (int i = 0; i <= 1000000; i++)

    {

        string s = to_string(i);

        int sig = 1;

        for (int k = 0; k < s.length(); k++)

        {

            for (int j = 0; j < n; j++)

            {

                if (s[k] - '0' == arr[j])

                {

                    sig = 0;

                    break;

                }

            }

            if (sig == 0)

                break;

        }

        if (sig == 0)

            continue;

        temp_min = min(temp_min, int(s.length() + abs(stoi(tc) - i)));

    }

    cout << min(temp_min, abs(stoi(tc) - 100));

}

 

하.. 정말쉽구나...그리고 화가나는ㄴ구나... 이 문제로 3시간을 써버렸어..