1107번-리모컨

중요 지식

---

round(pow(10, @)) : 부동소수점 계산으로 정확하지 않은 값이 나온다 그래서 반올림으로 값을 맞춰줘야함.

fill_n() : bool형은 선언을 하면 쓰레기값이 들어가므로 확실하게 초기화를 시켜야함 

 

코드

---

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int DownDist(int N, bool *onBtns){
    int count = 0, channel = 0, tN = N;
    int down = 0, maxBtn = 0;

    // 고장나지 않은 버튼중 가장 큰 버튼을 구함
    for(int i = 9 ; i >= 0; i--){
        if(onBtns[i]) {
            maxBtn = i;
            break;
        }
    }

    if(N == 0){
        channel = maxBtn;
    }
    // 1의 자리부터 채널 숫자와 작거나 같은 버튼을 구함
    for(int i = 0; tN > 0; tN/=10, i++){
        int num = tN%10;
        int btn = -1;

        // 채널숫자와 작거나 같은 버튼을 탐색  
        for(int j = num-down; j >= 0; j--){
            if(onBtns[j]) {
                btn = j;
                down = 0;
                break;
            }
        }

        // 탐색된 버튼이 채널 숫자보다 작다면 뒤에 있는 숫자를 전부 최대 버튼으로 바꾼다 : channel, maxBtn
        if(btn < num){    
            channel = 0;
            for(int j = 0; j < i; j++){
                channel += maxBtn * round(pow(10,j));
            }
        }
        
        if(btn == -1){
            down = 1;

            if(tN/10 == 0 && i > 0) {
                btn = 0;
            }else{
                for(int i = 0 ; i < 10; i++){
                    if(onBtns[i]) {
                        btn = i;
                        break;
                    }
                }
            }
        }

        channel += btn * round(pow(10,i));
    }

    count += abs(N - channel);

    for(count += 1; channel/10 != 0; count++){
        channel/=10;
    }

    return count;
}

int UpDist(int N, bool *onBtns){
    int count = 0, channel = 0, tN = N;
    int up = 0, minBtn = 0;

    // 고장나지 않은 버튼중 가장 작은 버튼을 구함
    for(int i = 0 ; i < 10; i++){
        if(onBtns[i]) {
            minBtn = i;
            break;
        }
    }
    
    if(N == 0){
        channel = minBtn;
    }
    // 한자리수부터 채널 숫자와 작거나 같은 버튼을 구함
    for(int i = 0; tN > 0; tN/=10, i++){
        int num = tN%10;
        int btn = 10;

        // 채널숫자와 작거나 같은 버튼을 탐색  
        for(int j = num+up; j < 10; j++){
            if(onBtns[j]) {
                btn = j;
                up = 0;
                break;
            }
        }
        
        if(btn == 10){
            up = 1;

            if(tN/10 == 0){ // 앞자리가 없다면 만든다
                for(int i = 1 ; i < 10; i++){
                    if(onBtns[i]) {
                        btn = i * 10 + minBtn;
                        break;
                    }
                }   
            }
        }

        // 탐색된 값이 채널 숫자보다 크다면 뒤에 있는 숫자를 전부 최소 버튼으로 바꾼다 : channel, maxBtn
        if(btn > num){    
            channel = 0;
            for(int j = 0; j < i; j++){
                channel += minBtn * round(pow(10,j));
            }
        }

        channel += btn * round(pow(10,i));
    }

    count += abs(N - channel);

    for(count += 1; channel/10 != 0; count++){
        channel/=10;
    }

    return count;
}

int Solution(int N, int M, bool *onBtns){
    int count;
    int upDist, downDist, nowDist;

    nowDist = abs(N - 100);

    if(M < 10){
        downDist = DownDist(N, onBtns);
        upDist = UpDist(N, onBtns);
        count = upDist > downDist ? downDist : upDist;
        count = nowDist > count ? count : nowDist;
    }else{
        count = nowDist;
    }
    
    

    return count;
}

int main(){
    int N, M;
    bool onBtns[10];
    fill_n(onBtns, 10, true);

    cin >> N;
    cin >> M;
    for(int i = 0; i < M; i++){
        int btn;
        cin >> btn;
        onBtns[btn] = false;
    }

    cout << Solution(N, M, onBtns);

    return 0;
}

풀이

---

최적의 거리을 구하기 위해서 3가지의 경우를 구해야 한다

바로 원하는 채널과 가장 가까우면서 보다 큰 조합 채널과 작은 조합 채널, 그리고 현재 채널의 경우이다

 

큰 조합 채널과 작은 조합 채널의 거리를 구하는 방법

1-1. 1의 자리부터 조사하는데 크거나 같은/작거나 같은 버튼을 찾아서 조합한다

1-2. 해당 버튼이 크다면/작다면 뒤에 있는 모든 값을 최소/최대 버튼의 값으로 바꾼다 (버튼을 못찾았을 때도 실행됨)

1-3. 해당 버튼을 찾지 못했다면 다음 조사에서 채널 값보다 큰/작은 버튼을 찾게한다 (up 또는 down 사용) 

만약 앞자리가 없거나 마지막 조사라면

큰 조합 채널의 경우 : (1보다 큰 최소 버튼) * 10 + (최소 버튼)을 조합한다 

작은 조합 채널의 경우 :  0을 조합한다, 원하는 채널이 한자리라면 가능한 아무 버튼을 조합한다

2. 원하는 채널에 구해진 채널을 빼서 차이를 count에 저장한다 (원하는 채널과 거리)

3. 구해진 조합 채널를 한자리씩 조사하면서 count를 더한다 (버튼을 누른 횟수)

 

현재 채널의 거리를 구하는 방법|원하는 채널 - 100| 이다

 

구해진 3가지 경우에서 가장 작은 횟수를 구하면 끝.!