백준 1107번: 리모컨

엄기훈·2023년 3월 5일

C 백준 브루트포스 알고리즘 알고리즘

알고리즘 풀이

목록 보기

8/9

❓ 문제

1107번: 리모컨

브루트포스 알고리즘은 많이 풀어본 적이 없어서 한 번 시도해봤다. 개인적으로 브루트포스 알고리즘은 그냥 모든 조건을 내가 일일히 생각해서 맞춰나갸야 해서 시간 소모가 큰 것 같다.

💡 풀이

가고자 하는 채널이 100번일 때
- 그 자리 그대로 이므로 0을 출력한다
고장난 버튼이 없는 경우
- +, -로만 눌러서 가는 경우와
- 바로 채널의 버튼을 눌러서 가는 경우의 최소값을 구하면 된다.
모든 버튼이 고장났을 때 (고장난 버튼이 10개 일 때)
- +, -로만 채널을 이동해야 하므로 원하는 채널과 100의 차이를 구한다.
고장난 버튼이 9개이고 0만 쓸 수 있는 경우
- +, - 버튼만 눌러서 이동하는 경우와
- 0을 누른 후 +, - 버튼을 눌러서 이동하는 경우의 최솟값을 구하면 된다.
그 외
1. 100번에서 1씩 더할 때
  - 누를 수 없는 버튼의 수를 제외하며 원하는 채널과 가장 가까운 채널을 구한다.
  - 그 채널의 자릿 수(만큼 버튼을 눌러야하므로) + +, - 버튼을 눌러 그 채널까지 가는 경우와
  - +, -로만 이동할 때 누르는 횟수의 최솟값을 구한다.
2. 100번에서 1씩 뺄 때
  - 누를 수 없는 버튼의 수를 제외하며 원하는 채널과 가장 가까운 채널을 구한다.
  - 이 때 0번 이하까지 가면 만족하는 채널이 없다는 뜻이므로 정답을 대충 가장 큰 수 500001로 설정한다.
  - 그 채널의 자릿 수(만큼 버튼을 눌러야하므로) + +, - 버튼을 눌러 그 채널까지 가는 경우와
  - +, -로만 이동할 때 누르는 횟수의 최솟값을 구한다.

⌨️ 전체 코드

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

using namespace std;

int main() {
    int targetChannel;
    int numOfBrokenButtons;
    int *brokenButtons = new int[numOfBrokenButtons];

    cin >> targetChannel >> numOfBrokenButtons;
    for (int i = 0; i < numOfBrokenButtons; i++) {
        cin >> brokenButtons[i];
    }

    if (targetChannel == 100) {
        cout << 0;
        return 0;
    }

    if (numOfBrokenButtons == 0) {
        cout << min(abs(targetChannel - 100), int(to_string(targetChannel).length()));
        return 0;
    }

    if (numOfBrokenButtons == 10) {
        cout << abs(targetChannel - 100);
        return 0;
    }

    if (numOfBrokenButtons == 9) {
        bool isZeroBroken = false;
        for (int i = 0; i < numOfBrokenButtons; i++) {
            isZeroBroken = brokenButtons[i] == 0;
            if (isZeroBroken)
                break;
        }
        if (!isZeroBroken) {
            cout << min(abs(targetChannel - 100), 1 + targetChannel);
            return 0;
        }
    }

    bool found = false;
    int channel = targetChannel;
    int numOfPush1;
    while (!found)
    {
        for (int i = 0; i < numOfBrokenButtons; i++) {
            string channelStr = to_string(channel);
            string buttonStr = to_string(brokenButtons[i]);
            if (channelStr.find(buttonStr) != string::npos) {
                found = false;
                break;
            };
            found = true;
        }
        if (!found) {
            channel++;
        }
    }
    numOfPush1 = min(int(to_string(channel).length() + (channel - targetChannel)),abs(targetChannel-100));

    found = false;
    channel = targetChannel;
    int numOfPush2;
    while (!found)
    {
        for (int i = 0; i < numOfBrokenButtons; i++) {
            string channelStr = to_string(channel);
            string buttonStr = to_string(brokenButtons[i]);
            if (channelStr.find(buttonStr) != string::npos)
            {
                found = false;
                break;
            };
            found = true;
        }
        if (!found) {
            channel--;
        }
        if (channel < 0) {
            break;
        }
    }
    numOfPush2 = min(int(to_string(channel).length() + (targetChannel - channel)),abs(targetChannel-100));
    if(channel < 0) {
        numOfPush2 = 500001;
    }

    cout << min(numOfPush2, numOfPush1);
}