백준 1107 리모컨 c++ [컴공과고씨]

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

1107번: 리모컨

해결하는 방법은 브루트 포스 방식을 이용해서 풀어주었다.

문제를 풀때 3단계로 나눠서 풀어주었는데 그 방식을 정리해보았다.

 

1. bool형 배열을 생성 -> 이 배열에는 채널이 번호를 눌러서 만들어 질 수 있는지를 저장한다.

그래서 없는 버튼이 들어가있는 채널에는 false 넣어준다. 이 때 버튼이 있는지 없는지를 확인하는 방법은 채널을 string으로 바꾸어주고 처음에 버튼을 입력받을 때 char로 입력을 받아 string의 find 함수를 통해서 채널에 없는 버튼이 포함이 되어있는지 확인하는 방법으로 구현해주었다.

 

2. 목표 채널로 부터 버튼으로 만들 수 있는 가장 가까운 채널을 찾음

 

 

3. 마지막으로 위 에서 찾은 각각의 채널에서 자리수를 더해주면 그것이 리모컨을 눌러야할 수가 된다.

이유는 4000을 번호를 누를때는 자리수 만큼 즉, 4번 숫자 버튼을 눌러 주어야한다.

자리수를 확인하는 것은 채널을 string으로 변환후 length()함수를 이용하였다.

-> 리모컨 누르는 수 = (+ or - 버튼을 누르는 수) + (숫자 버튼 누르는 수)

-> abs(result -n) + to_string(result).length();

이 두개의 결과와 100번에서 그냥 + or -를 눌러서 갈 수 있는 수를 비교해주면 끝이다.

참고로 n == 100일때는 0을 출력해주면 된다.

 

 

전체 코드

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
    int n, m;
    char button[11]; // find함수를 쓰기 위해서 char로 입렵받음
    bool channels[1000002];//채널을 만들수있는지 저장
    cin >> n >> m;
    for (int i = 0; i < m;i++){
        cin >> button[i];
    }
    string num;
    int result = 99999999;
    int result2 = 99999999;
    if(n != 100){
        for (int i = 0; i < 1000001; i++){
            channels[i] = true; 
            num = to_string(i);//채널을 string으로 바꿈 (비교를 위해서)
            for (int j = 0; j < m;j++){
                if(num.find(button[j]) != std::string::npos){
                    channels[i] = false;
                    break;
                }//find 함수를 통해 고장난 버튼이 포함된 경우 false
            }
        }
        channels[100] = true;//채널 100부터 시작하기 때문에 true
 
        //목표 채널로 부터 버튼으로 만들 수 있는 가장 가까운 채널을 찾음
        for (int i = n; i >=0 ;i--){ // n보다 작은 채널에서 탐색
            if(channels[i]){
                result = i;
                break;
            }
        }
        for (int i = n; i < n + abs(n - 100); i++){
            if(channels[i]){
                result2 = i;
                break;
            } // n보다 큰 채널에서 탐색
        }
 
        //각 채널 비교
        int first = abs(result - n) + (to_string(result).length());
        // 작은 채널까지 가는데 눌러야하는 수
        // + or - 버튼 누르는 수 + 숫자 버튼 누르는 수
 
        int second = abs(result2 - n) + (to_string(result2).length());
        // 큰 채널까지 가는데 눌러야하는 수
 
        int third = abs(100 - n);
        //채널 100번에서 그냥 + or - 리모컨을 눌러서 가는 수
 
        //비교하여 최소 값을 찾아 줌
        if(first <= second){
            if(first < third){
                cout << first;
            }else{
                cout << third;
            }
        }else if(first > second){
            if(second < third){
                cout << second;
            }else{
                cout << third;
            }
        }
    }else{
        cout << 0;
    }
    return 0;
}
 

 

 

체감 난이도	걸린시간	참고	사용 알고리즘	기타
중	1.5h	x	브루 포스(brute force)	중간에 포문 범위 잘못 잡아서 푸는데 오래걸림.

 

yea!