백준 1107번 리모컨

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

1107번: 리모컨

문제

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

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

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

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

 

입력

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

 

출력

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

 

풀이

우선, 이 리모컨 문제는 2달 전에 시도를 했었는데 결국 예외 Case를 못 찾아내서 포기했던 문제이다.

이런 브루트 포스 알고리즘 문제는 비교적 간단하게 해답을 찾아낼 수 있지만, 항상 예외 처리 부분에서 급격한 탈모증세가 오는 느낌을 받기 마련이다. 때문에 이번엔 최대한 간단간단하게 코드를 짜려고 노력하다 보니 답을 맞힐 수 있었다.

각설하고,

이 문제는 두 가지 Case가 존재한다.

1. 현재 채널(100번)에서 오직 +/- 버튼만을 이용하여 이동하려는 채널 N까지 가는 경우
2. 채널 N에서 최대한 가까운 채널의 숫자 버튼을 누른 후 +/- 버튼을 이용하는 경우

우선, 첫 번째 사례를 넣은 이유는 만약 N이 99 나 101인 경우 고장 난 버튼을 볼 것도 없이 +/- 버튼으로 해결 가능할 뿐 아니라 2번 Case로 채널을 돌리려면 더 많이 누르게 된다.

따라서 1번과 2번 Case의 경우 누르는 버튼의 최솟값이 문제의 답이다.

하지만, 문제는 2번 사례이다. 2번에서 헷갈릴 수 있는 사례는

1. 문제에서 N의 조건이 (0 <= N <= 500,000)이지, 이동할 수 있는 채널이 50만까지가 아니다. 따라서 50만의 2배인 100만까지 갈 수 있는 것으로 생각하고 풀어야 한다.

2. 보통 채널을 이동할 때 그 채널의 자릿수를 계산하고, 자릿수만큼 정답에 더해줘야 하는데

만약 이동하고 하자는 채널이 0번인 경우 자릿수 계산에서 예외처리를 꼭 해주어야 한다.

이 두 가지에 걸려서 몇 번 헤매었다...

 

 소스코드

#include <iostream>
#include <algorithm>
#include <cstdbool>
#include <vector>
using namespace std;
 
int n, m;  //이동하려는 채널 n, 고장난 버튼의 개수 m
bool break_btn[10];
 
int simple_case() { //단순히 +/- 버튼만을 이용
    if (n >= 100) return n - 100;
    else return 100 - n;
}
 
int press(int t) { //누를 수 있는 채널인지 체크 + 자릿수 반환
    if (t == 0) { // 예외 : 0일때
        if (break_btn[0]) return 0;
        else return 1;
    }
    else {
        int len = 0;
        while (t) {
            int temp_t = t % 10;
            if (break_btn[temp_t]) return 0;
            len++;
            t /= 10;
        }
        return len;
    }
}
int press_chn() {
    int ans = 1000001;
    for (int i = 0; i <= 1000000; i++) {
        int temp_i = i;
        int len = press(temp_i);
        if (len > 0) {
            int press = temp_i - n;
            if (press < 0) press = -press;
            if (ans > len + press) {
                ans = len + press;
            }
        }
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int temp; scanf("%d", &temp);
        break_btn[temp] = true;
    }
    int ans = min(simple_case(), press_chn());
    printf("%d", ans);
    return 0;
}

추가 설명

int press_chn() {
    int ans = 1000001;
    for (int i = 0; i <= 1000000; i++) {
        int temp_i = i;
        int len = press(temp_i);
        if (len > 0) {
            int press = temp_i - n;
            if (press < 0) press = -press;
            if (ans > len + press) {
                ans = len + press;
            }
        }
    }
    return ans;
}

 

• press_chn 함수는 0~100만까지 돌면서 누를 수 있는 번호를 press 함수에서 찾고 동시에 길이를 반환시켜 기존 정답보다 작으면 정답을 초기화하는 함수이다.

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~