[백준 C++] 1107 리모컨 - 브루트포스

1107번: 리모컨

cpp

#include <iostream>
#include <string>
using namespace std;

int N, M, C;
bool Broken[10];

bool IsPossible(string CurrentChannel, int Size)
{
‌for (int i = 0; i < Size; ++i)
‌{
‌‌int Number = CurrentChannel[i] - '0';
‌‌if (Broken[Number])
‌‌{
‌‌‌return false;
‌‌}
‌}

‌return true;
}

int CountPush(int Target)
{
‌int Push = 1000000;

‌for (int Current = 0; Current <= 1000000; ++Current)
‌{
‌‌string CurrentChannel = to_string(Current);
‌‌int Size = CurrentChannel.size();
‌‌if (!IsPossible(CurrentChannel, Size))
‌‌{
‌‌‌continue;
‌‌}

‌‌Push = min(Push, abs(Target - Current) + Size);
‌}

‌return Push;
}

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

‌cin >> N >> M;

‌for (int i = 0; i < M; ++i)
‌{
‌‌int Button;
‌‌cin >> Button;
‌‌Broken[Button] = true;
‌}

‌cout << min(abs(N - 100), CountPush(N));
}

---

브루트포스 알고리즘 유형의 문제입니다.

다음 두 가지 상황 중에 더 작은 값을 선택하도록 해서 풀었습니다.

 

1. 현재 채널(100)에서 목표 채널(N)까지 +,- 버튼만 사용했을 때의 횟수: abs(N - 100)

2. 숫자 버튼 입력 후 +, - 버튼 사용을 통해 목표 채널까지 이동했을 때의 횟수

 

2번 단계에서는 숫자 버튼으로 입력한 채널로 0부터 1000000까지 모두 탐색해줍니다.

그리고 각 채널 마다 숫자 버튼으로 입력 가능한지 확인한 후,

입력 가능하다면 +,-로 이동하는 횟수{abs(목표채널 - 해당 채널)} + 숫자 버튼 입력 횟수{해당 채널의 길이}를 구해주고

그 중 가장 작은 값을 출력하도록 해줍니다.