Written by JS970
on February 18, 2023

1107 - 리모컨

난이도: 골드 5
날짜: 2023년 2월 18일
상태: Correct
추가 검토 여부: No
알고리즘 : 브루트포스

solution

전역 배열 valid를 만들어서 고장난 버튼을 사용하지 못하도록 한다.
possible() upward_search(), downward_search()를 구현하였다.
- possible은 고장난 버튼 때문에 한번에 채널을 누를 수 없다면 false, 고장난 버튼과 관계없이 채널을 누를 수 있다면 true를 반환한다.
- upward_search는 입력받은 인자에 대해 possible이 true를 반환할 때까지 입력받은 인자를 1씩 증가시킨다. possible이 true를 반환하면 이 값을 return한다.
- downward_search는 upward_search와 동일하게 동작하지만 인자를 1씩 감소시키며 탐색한다.
위의 세 함수를 이용하여 바꾸고 싶은 채널(N)에 대해 +버튼과 -버튼을 가장 적게 눌러도 되는 값인 up과 down을 초기화시킨다.
100번 채널에서 시작하므로 변경할 채널을 직접 입력하는 것보다 100번 채널에서 직접 + - 버튼을 통해 이동하는 것이 더 빠를 경우를 생각한다. 이는 뺄셈 연산으로 구현 가능하다.
위의 로직으로 이 문제를 풀 수 있으나 아래의 주의사항을 유념해서 코딩해야한다.
- 0번 버튼 빼고 모든 버튼이 고장났을 때 up은 논리적으로 계산할 수 없으므로 무한루프가 발생한다. 이를 처리해 주어야 한다.
- up과 down의 값이 같을 경우 down값을 선택하도록 코딩해야 한다(999가 1000보다 버튼을 적게 누르기 때문이다)
- down값이 음수가 되어서는 안된다.
- 바꾸고 싶은 채널(N) - down값이 음수가 되어서는 안된다.
위 네 가지 반례를 생각하지 못해서 한번 틀렸다. 이런 반례들을 확실하게 처리하는 연습을 해야겠다.

code

#include <iostream>
#include <string>
using namespace std;

int upward_search(int);
int downward_search(int);
bool possible(int);
bool valid[10] = {true, true, true, true, true, true, true, true, true, true};

bool possible(int alter)
{
    string alter_s = to_string(alter);
    for(int i = alter_s.length()-1; i >= 0; i--)
    {
        int idx = alter_s[i] - '0';
        if(!valid[idx]) return false;
    }
    return true;
}

int upward_search(int alter)
{
    while(!possible(alter)) alter++;
    return alter;
}

int downward_search(int alter)
{
    while(!possible(alter) && alter >= 0) alter--;
    return alter;
}

int main()
{
    int N, M;
    cin >> N >> M;
    int invalid;
    for(int i = 0; i < M; i++)
    {
        cin >> invalid;
        valid[invalid] = false;
    }

    int num, distance, up, down;
    if(!possible(N))
    {
        bool zero = true;
        for(int i = 1; i < 10; i++) 
        {
            if(valid[i]) zero = false;
        }
        if(!zero) up = upward_search(N);
        down = downward_search(N);
        if(up-N >= N-down && N-down > 0 && down >= 0)
        {
            distance = N-down;
            num = down;
        }
        else
        {
            distance = up-N;
            num = up;
        }
    }
    else 
    {
        distance = 0;
        num = N;
    }

    int _100man = (N > 100) ? N-100 : 100-N;

    string num_s = to_string(num);
    int button = (_100man > num_s.length() + distance) ? num_s.length() + distance : _100man;
    cout << button << endl;

    return 0;
}

ref

1107번: 리모컨

Top