Dong-kipedia

BOJ 1107 리모컨

 
  • Nov 13, 2021
  • 0 views

문제 링크

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

알고리즘 유형

브루트 포스

시간복잡도

브루트 포스의 시간 복잡도는 \(O(경우의\ 수\times 각\ 경우의\ 시간\ 복잡도)\)

경우의 수

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

숫자 버튼 선택

숫자 버튼으로 주어진 채널 N과 가장 가까운 채널을 생성해야 한다.

고장난 버튼을 제외하는 시점에 따라 2가지 방법 존재

  1. 고장난 버튼을 제외하고 채널 생성
  2. 생성된 채널 중 고장난 버튼 포함하는 채널 제외

두 방법 모두 고장난 버튼이 없을 경우 0 ~ 9 모든 버튼으로 생성할 수 있는 채널 N개를 모두 생성해야 한다.
여기까지의 시간 복잡도는 \(O(N)\)이다.
하지만 2번의 경우 생성된 채널의 각 자리수가 고장난 버튼인지 확인해야 한다.
N에는 총 \(logN\)의 자리수가 존재하기 때문에 2번의 시간복잡도는 \(O(N \times logN = NlogN)\)이다.

시간복잡도가 낮은 1번을 채택한다.

+/- 버튼 선택

숫자 버튼으로 생성한 채널에서 N까지 거리만 구하면 된다. 따라서 시간복잡도는 O(1)

각 경우의 시간 복잡도

별도 요구되는 연산 없음

총 시간 복잡도

\(O(N \times 1 = N)\)

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int N, M;
bool err_dgt[10];
vector<int> dgts;
int chl_len;
int answer;

void bf(int pos, int chl){
    // 숫자 버튼을 1회 이상 눌렀다면 생성된 채널과 N의 거리의 최솟값 갱신
    if (pos) {
        answer = min(answer, pos + abs(N - chl));
    }
    
    // 주어진 채널보다 자리수가 1 더 긴 채널까지만 생성한다.
    if (pos > chl_len) return;

    // 이번 자리수 선택
    for (int dgt : dgts) {
        bf(pos + 1, chl * 10 + dgt);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int dgt;
        cin >> dgt;
        err_dgt[dgt] = true;
    }

    // 사용할 수 있는 자리수의 벡터 dgts 초기화
    for (int dgt = 0; dgt < 10; ++dgt) {
        if (err_dgt[dgt]) continue;
        dgts.push_back(dgt);
    }

    // 정답의 초기값은 숫자 버튼을 누르지 않는 경우
    answer = abs(N - 100);

    // 숫자 버튼을 눌러서 채널 생성
    chl_len = to_string(N).size();
    bf(0, 0);

    cout << answer;

    return 0;
}
Search