백준 1107 리모컨 (C++)

안유태·2022년 9월 5일
0

알고리즘

목록 보기
32/239
post-custom-banner

1107번: 리모컨

생각이 많이 필요했던 브루트 포스 문제이다. 버튼을 최소 몇번 누르는지 구하는 문제였는데 여러 조건들이 떠오르면서 생각이 많아졌었다. 우선 채널의 시작은 100번이라는 것, 그리고 101, 99와 같이 +, - 만으로 가는게 더 빠른 경우, 그리고 버튼이 고장나 눌리지 않는 경우도 있다.
최소 숫자를 구해야 하기 때문에 우선은 최소 거리의 숫자와 N의 절댓값 차를 구하면 된다고 판단했다. 브루트 포스 이기에 처음부터 끝까지 반복문을 돌려주려 했는데, 버튼이 5,6,7,8,9가 눌리지 않을 경우를 생각하면 최대 채널이 1,000,000이 되서 시간 초과가 나지 않을 까 걱정을 좀 했었다.
반복문을 돌면서 isTrue 함수로 해당 채널에 눌리지 않는 버튼 숫자가 포함되있는지 확인을 했고 없다면 채널 숫자의 번호 갯수와 N과의 절대값 차를 구해 res와 비교하여 작은 값을 저장해두었다. res의 초기값은 abs(N-100)으로 주었다.
생각이 많이 필요했고 최대 채널은 다른 분의 풀이를 참고했다.



#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int N, M;
bool A[10];

bool isTrue(int n) {
    string tmp = to_string(n);

    for (int i = 0; i < tmp.size(); i++) {
        if (A[tmp[i] - '0']) {
            return false;
        }
    }

    return true;
}

void solution() {
    int res = abs(N - 100);

    for (int i = 0; i < 1000000; i++) {
        if (isTrue(i)) {
            int a = abs(N - i) + to_string(i).size();
            res = min(res, a);
        }
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> M;

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

    solution();

    return 0;
}
profile
공부하는 개발자
post-custom-banner

0개의 댓글