[ C++ ] 백준 1107: 리모컨

 

안녕하세요? 수구리입니다.

이번 포스팅에서는 백준 문제 중에서 브루트 포스 알고리즘에 대한 문제를 풀어보려고 합니다.

조만간 브루트포스 알고리즘에 대한 포스팅도 추가로 해야겠네요.

간단하게만 적어보자면.. 브루트 포스(Brute Force)는 우리나라 말로는 "완전 탐색"이라고 합니다.

알고리즘 이론 책들을 보면 가장 앞쪽에 나와있는 단원에 속하고요.

보통 일단 문제를 접하게 되면 가장 먼저 이 방법을 통해서 문제를 해결해보려고 시도를 합니다.

이 알고리즘으로 대부분 해결이 되지만, 탐색을 해야 하는 범위가 많아지면 시간이 오래 걸려 효율성 측면에서 걸리게 되는 경우도 있죠.

아무튼 나중에 더 자세히 알아보도록 하고 백준 리모컨에 대한 문제는 아래 링크에 걸어두겠습니다.

 

 

 

[ 문제 ] 백준 1107: 리모컨

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

1107번: 리모컨

 

 

 

[ 나의 풀이 ]

/*
 date : 2021.12.16
 problom : 1107
 title : 리모컨
 discribe : 채널 100에서 N으로 이동하는데, 사용하지 못하는 리모컨 번호를 고려해서 최소한의 버튼 클릭으로 이동해보자.
*/

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

// 리모컨의 숫자 버튼 상태를 나타내는 vector
// 0 : 정상, 1 : 고장
vector<bool> remote(10);

// 입력 : n (0 ~ 1000000) - 이동하려고 하는 채널
//       -  1000000까지인 이유? 
//          => 문제에서 이동하려고 하는 채널 N의 범위가 0 ~ 500000 이지만,
//             이동하려는 채널보다 높은 위치에 있을 때 감소하는 범위도 고려해야 하므로..
// 출력 : len - 리모컨을 누른 횟수
int check(int n) {
    // 이동하려고 하는 채널이 0인 경우
    if (n == 0){
        if (remote[0]){
            // 리모컨의 "0" 버튼이 고장난 경우
            return 0;
        } else {
            // 리모컨의 "0" 버튼이 정상인 경우 : 리모컨으로 0을 누르면 되므로 1을 리턴
            return 1;
        }
    }

    // 이동하려고 하는 채널이 0이 아닌 경우
    int len = 0;
    // 각 자리수에 대해서 나머지 연산을 통해 한 자리수씩 뽑아내어 고장난 버튼이 있는지 판별
    while(n > 0){
        // 리모컨의 버튼이 고장난 경우
        if (remote[n % 10])
            // remote[3456 % 10] = remote[6] => 리모컨의 6 버튼이 고장인 경우
            return 0;
        
        // 리모컨의 버튼이 고장나지 않은 경우
        n = n / 10;
        len += 1;
    }
    // 리모컨을 누른 횟수 반환
    return len;
}

int main(){
    // N : 이동하려고 하는 채널
    // broke : 리모컨의 고장난 숫자의 개수
    int N, broke = 0;    
    cin >> N >> broke;
    
    // 고장난 숫자의 개수만큼 반복
    for (int i=0; i < broke; i++){
        int x;
        cin >> x;
        // 고장난 숫자에 대한 bool값 true로 변경
        remote[x] = true;
    }
    
    // count : 리모컨을 누른 최소 횟수
    int count = abs(N - 100); // 최초로 연산자(+,-)만 사용해서 몇번 눌러야 이동할 수 있는지 계산

    // 리모컨의 숫자를 누른 횟수를 구하기 위한 반복문 : 브루트포스 알고리즘
    for (int i=0; i <= 1000000; i++){
        int c = i;
        // len : c에 대해 반환된 리모컨을 누른 횟수
        int len = check(c);
        // 만약 len이 0보다 크다면
        if (len > 0) {
            // press : 누른 번호에서 이동하려하는 채널까지의 사용해야 하는 연산자(+, -) 횟수 계산
            int press = abs(c - N);
            // 최초 100번 채널에서, 연산자만 가지고 몇번을 눌러야 도달할 수 있는지에 대한 count 변수와,
            // (리모컨에서 누른 번호에서부터 이동하려하는 채널까지 연산자를 눌러야하는 횟수)
            // + (c에 대해 반환된 리모컨을 누른 횟수)를 비교하여 더 작은 값을 count에 저장
            if (count > press + len)
                count = press + len;
        }
    }
    // 최종적으로 가장 최소의 값을 출력
    cout << count;
    return 0;

}

 

 

위의 코드 주석에 설명을 적어두었습니다. 질문 및 기타 지적은 환영입니다..!

이상으로 백준의 브루트 포스 알고리즘 문제인 리모컨을 풀어보았습니다.

감사합니다.