백준 1107번 리모컨

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

N=500,000까지이지만 5 6 7 8 9가 망가졌을 경우도 고려해야하기 때문에 MAX를 1,000,000+1까지 설정해야했던 문제였습니다.

일차적으로 이 부분에서 틀렸던 문제이고 이차적으로는 length 함수에서 0에 대해 예외처리를 하지 않았기 때문에 틀렸던 문제였습니다.

알고리즘 자체는 간단한 브루트포스였습니다.

1. 기존 채널 100에서 +/- 버튼을 클릭하는 경우

2. 채널을 입력하고 +/- 버튼을 클릭하는 경우

위 두 가지 경우 중 최소를 반환하는 값이 정답이였습니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

 

const int INF = 987654321;

//2 3 4 5 6 7 8 9를 입력 못하는 경우도 고려

const int MAX = 1000000 + 1;

 

int N, M;

vector<int> broken;

 

//현재 채널에서 바꾸는 경우

int changeFromHundred(void)

{

        return abs(N - 100);

}

 

//해당 채널을 누르는 것이 가능한지 여부

//고장난 버튼을 누르면 false

bool possible(int num)

{

        if (num == 0)

                 if (find(broken.begin(), broken.end(), 0) == broken.end())

                         return true;

                 else

                         return false;

 

        while (num)

        {

                 if (find(broken.begin(), broken.end(), num % 10) != broken.end())

                         return false;

                 num /= 10;

        }

        return true;

}

 

//누른 채널의 길이

int length(int num)

{

        //0이면 길이 1(중요한 예외처리)

        if (num == 0)

                 return 1;

 

        int result = 0;

        while (num)

        {

                 num /= 10;

                 result++;

        }

        return result;

}

 

//100에서 시작이 아닌 채널을 누르고 나서 +/-

int changeEntirely(void)

{

        int result = INF;

        int similar = 0;

 

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

        {

                 //해당 채널을 누를 수 있다면

                 if (possible(i))

                 {

                         int click = abs(N - i); //+/-을 몇 번 눌러야하는지 확인

                         if (result > click) //덜 클릭해도 된다면

                         {

                                 result = click;

                                 similar = i; //해당 숫자 저장

                         }

                 }

        }

       

        return result + length(similar);

}

 

int main(void)

{

        cin >> N >> M;

 

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

        {

                 int button;

                 cin >> button;

                 broken.push_back(button);

        }

 

        cout << min(changeFromHundred(), changeEntirely()) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~