[BOJ] 백준 1107 리모컨

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

 Input 

5457

3

6 7 8

 

 Output 

6

 

① 숫자 버튼 없이 +,-로만 조작하는 경우

    abs(N - 100);

② 숫자 버튼으로 이동 후 +,-로 조작하는 경우

    모든 채널에 대해서 고장 버튼을 고려해서 이동가능한지 확인 후,

    해당 채널에서 +,-를 몇 번 눌러야 하는지 확인합니다.

 

Q. N의 최대값은 500,000인데 0 ~ 1000,000채널까지 탐색하는 이유?

A. 고장난 버튼에 따라서 50만 위에서 -버튼을 누르는게 좋을 수도 있기 때문에 여유롭게 크기를 잡음

 

Q. 수학적인 접근 방법이 있을까?

N 채널의 차이를 최소로해서 Greedy 방식으로 접근할 수 있지만,

 Input 

1555

8

0 1 3 4 5 6 7 9

 

 Output 

670

① 초기 100번에서 +,- 버튼으로만 이동 시

    abs(1555 - 100) = 1,455번

② 숫자 버튼 활용하는 Case

    ▷ 1과 차이가 최소인 버튼인 2를 선택 (1회)

    ▷ 5와 차이가 최소인 버튼인 2를 선택 (2회)

    ▷ 5와 차이가 최소인 버튼인 2를 선택 (3회)

    ▷ 5와 차이가 최소인 버튼인 2를 선택 (4회)

    ▷ 667 번 -버튼 클릭 (2222 - 1555)

    → 4번 + 667번 = 671번

③ 실제 정답 Case

    ▷ 888 번호 선택 (8을 3번 누름)

    ▷667번 +버튼 클릭 (1555 - 888)

    → 3번 + 667번 = 670번

▶ 수식을 이용해서 접근할 수도 있지만, 모든 채널을 완전 탐색하는 것이 좀 더 간단!

---

#include <iostream>
using namespace std;
#define MAX 1000000
 
bool broken[10]; // 0~9
 
// 숫자버튼으로 이동할 수 있는 경우 몇번 눌러야하는지 반환(= 채널의 길이)
int isPossible(int channel){
    if (channel == 0)
        // 고장난 경우: 0, 고장나지 않은 경우: 1 
        return broken[0] ? 0 : 1;
    
    int len = 0;
    while (channel > 0){
        // 고장난 경우 0 반환
        if (broken[channel % 10]) 
            return 0;
        len += 1;
        channel /= 10;
    }
    return len;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int N, M, answer, btnCnt;
    cin >> N >> M;
 
    int brokenBtn;
    while (M--) {
        cin >> brokenBtn;
        broken[brokenBtn] = true;
    }
 
    // 숫자 버튼 없이 +,-만으로 조작했을 때,
    answer = abs(N - 100);
 
    // 숫자 버튼으로 특정 채널로 이동한 후 +,- 조작 수 확인
    for (int channel = 0; channel < MAX; channel++) {
        
        // 숫자버튼으로 이동가능한 채널인지 확인
        btnCnt = isPossible(channel);
        if (btnCnt > 0) {
            // 숫자버튼으로 이동 후 필요한 +,- 버튼 횟수
            btnCnt += abs(N - channel);
            // 기존값과 비교해서 최소 버튼 횟수로 갱신
            answer = answer < btnCnt ? answer : btnCnt;
        }
    }
    
    cout << answer << '\n';
}