백준 1107번 리모컨

🔒[문제 url]

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

🔑알고리즘

2초로 시간 제한이 넉넉하기때문에, 모든 채널을 조회하여 최소값을 찾는
Brute Force 알고리즘을 적용한다.

1. 고장난 버튼이 있는지 탐색을 하기위해 채널은 string으로 입력받는다.
2. + -로 이동하는 횟수인 ans = abs((stoi(n)) - 100)으로 초기화한다.
3. i = 0부터 i = 1,000,000까지 탐색하며, 입력 가능한 채널인지 검사한 후 최소값을 갱신한다.
이때 갱신값은 채널 입력 횟수to_string(i).length()와 + -입력 횟수abs(stoi(n) - i)의 합이다.

• 탐색 시 주의할 점은?
  • N의 최대값은 500,000이지만, -를 통해 내려가는 것이 더 빠를 수 있으므로 탐색 범위는 0 <= i <= 1,000,000이다.

🐾부분 코드

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	memset(button, true, sizeof(button));
	for (int i = 0; i < m; i++)
	{
		int x; cin >> x;
		button[x] = false;
	}

}

<입력 및 초기화 함수>
bool type 배열 button을 선언해주어 모두 true로 초기화한 뒤,
입력받는 버튼에 대해 false 처리하여 고장난 버튼임을 확인하는데 사용한다.

bool canInput(string s)
{
	for (int i = 0; i < s.length(); i++)
	{// 입력하려는 채널번호에 고장난 버튼이 있다면 입력 불가
		if (!button[s[i] - '0']) return false;
	}
	return true;
}

<채널 입력 가능 여부 확인>
문자열로 입력받은 채널의 모든 자릿수를 조회하며, 고장난 버튼이 있다면 false를 반환, 입력 가능하다면 true를 반환한다.
s[i]는 char type이므로 ascii code를 통해 indexing해야한다.

void SOLVE()
{
	ans = abs(stoi(n) - 100);

	for (int i = 0; i <= 1'000'000; i++)
	{
		if (canInput(to_string(i)))
		{
			int temp = abs(stoi(n) - i) + to_string(i).length();
			ans = min(ans, temp);
		}
	}
	cout << ans;
}

<최소값 갱신 및 출력>
위에서 설명한 알고리즘에 따라, 모든 채널을 방문하며 입력 가능한 채널인지 확인하고
최소값을 갱신한다.
i의 범위에 주의한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

string n;
int m;
bool button[10];

int ans = 0;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	memset(button, true, sizeof(button));
	for (int i = 0; i < m; i++)
	{
		int x; cin >> x;
		button[x] = false;
	}

}

bool canInput(string s)
{
	for (int i = 0; i < s.length(); i++)
	{// 입력하려는 채널번호에 고장난 버튼이 있다면 입력 불가
		if (!button[s[i] - '0']) return false;
	}
	return true;
}

void SOLVE()
{
	ans = abs(stoi(n) - 100);

	for (int i = 0; i <= 1000'000; i++)
	{
		if (canInput(to_string(i)))
		{
			int temp = abs(stoi(n) - i) + to_string(i).length();
			ans = min(ans, temp);
		}
	}
	cout << ans;
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

백준을 하지않고 존재만 알고있던 시절에 누군가 이 문제로 머리 싸매는 것을 보면서, '와.. 저런걸 진짜 어떻게 풀지?' 라고 생각했던 때가 기억난다.
solved.ac 클래스 밀기를 하던중 만나 너무 반가워 풀었더니, 너무 쉽게 풀려 꽤나 신선한 기분이 들었다. 많이 성장했나보다.