[BOJ] 1107 리모컨

많은 사람들이 문제 풀다가 리모컨을 부셔버리고 싶다는 그 문제..

실생활 문제이다.

1. 기본 채널이 100번 채널이다. 최소 채널은 0번 채널이고 최대 채널은 무제한이다.
2. n번 채널로 이동하고 싶은데, 리모컨의 숫자부분이 몇 개 부셔서 있다.
3. 채널은 위아래로 조작할 수 있다.(위아래는 부서지지 않음)
4. 최소한 리모컨을 써서 n번째 채널로 이동할 때, 몇 번 동작하는가?

깊게 생각해보기

9번이 고장나고 99번 채널로 이동할 때 리모컨을 조작하는 프로세스는 아래 3가지다.

• 채널을 한칸 내린다. (1번 동작)
• 99번을 기준으로 위로 가장 가까운 채널을 찾는다.(100번 채널 -> '1' '0' '0' 3번 동작)
  • 아래로 한칸 내린다. (1번 동작, 총 4번)
• 99번을 기준으로 아래로 가장 가까운 채널을 찾는다. (88번 채널 -> '8' '8' 2번 동작)
  • 위로 열한칸 올린다. (11번 동작, 총 13번)

따라서 채널을 한칸 내리는 것이 정답이다.

이를 일반화하면 3가지 방법이 있다.

• 채널을 위아래로 조작하는 방법(리모컨 숫자 사용 x)
• target 채널을 기점으로 위로 가장 가까운 채널 찾는 방법
• target 채널을 기점으로 아래로 가장 가까운 채널 찾는 방법

예외사항 고려하기

target 채널을 기점으로 가까운 채널 찾을 때 주의할 점은 위로 찾을 때는 최대 채널이 무한이므로
target 채널이 500,000이고, 고장난 리모컨 버튼이 {1,2,3,4,5,7,8,9}이면
600,000 채널로 이동해서 채널을 아래로 조작하면 100006번 만에 도달할 수 있다.
아래로 찾을 때도 마찬가지.

자리 바뀜도 조심해야한다.
target 채널이 10이고, 고장난 리모컨 버튼이 {1,0}이면
9로 이동해서 채널을 위로 조작하면 2번만에 도달할 수 있다.

소스코드

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

// 고장난 리모컨 버튼
bool broken[11]={false};

// 리모컨을 조작한 횟수 구하기 11이면 2번 조작 -> 2, 1123이면 4번 조작 -> 4
int get_channel_length(int channel) {
    string chnl = to_string(channel);
    return chnl.size();
}

// 리모컨을 조작하여 만들 수 있는 채널인지 검사
bool check(int n) {
    while(n >= 10) {
        if(broken[n%10] == true) {
            return false;
        }
        n /= 10;
    }
    if(broken[n] == true) {
        return false;
    }
    return true;
}

int top_down(int target_channel) {
    cout << "top_donw==========\n\n\n";
    int click_cnt = 1000000; // 0으로 초기화 하면 반복문을 통과할 경우 최소값으로 비교될 수 있기 때문
    for(int k = target_channel; k <= 1000001;k++) { // target 채널에서 리모컨으로 이동 가능한 가장 가까운 채널 찾기
        cout << "K: " << k << endl;
        if(check(k)){
            click_cnt = k - target_channel;         // 아래로 조작하는 횟수
            click_cnt += get_channel_length(k);     // 리모컨 조작 횟수
            break;
        }
    }
    cout << "top_down: " << click_cnt << ", target_channel: " << target_channel << endl;
    return click_cnt;
}

int bottom_up(int target_channel) {
    cout << "bottom_up==========\n\n\n";
    int click_cnt = 2000000;
    for(int k = target_channel; k >= 0; k--) {
        cout << "K: " << k << endl;
        if(check(k)){
            click_cnt = target_channel - k;
            click_cnt += get_channel_length(k);
            break;
        }
    }
    cout << "bottom_up: " << click_cnt << ", target_channel: " << target_channel << endl;
    return click_cnt;
}

int click(int cur_channel, int target_channel) {
    cout << "click only: " << abs(cur_channel - target_channel) << endl;
    return abs(cur_channel - target_channel);
}


int main(int argc, char *argv[])
{
    // 채널의 최소는 0, 기본 100
    int n;  // 목표 채널
    int m; // 고장난 채널 개수
    int channel = 100;
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin >> n >> m;


    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        broken[temp] = true;
    }

    if(n == channel) {
        cout << 0;
    }
    else {
        int td = top_down(n);
        int bu = bottom_up(n);
        int c = click(channel, n);
        int ans = min(min(td, bu), c);

        cout << ans << endl;
    }
    return 0;
}

이스터에그

 

푸는데 꼬박 1년 걸렸습니다. 너무 조급해하지 마세요. 여러분들은 저보다 더 빠르게 풀 수 있잖아요 ㅎㅎ