1107. 리모컨

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

원하는 채널로 가기 위한 최소로 누를 버튼의 수를 구하는 문제이다.

일일이 경우를 따져보려면 아무래도 너무 많기 때문에 일일이 다 눌러보면서 적절한 방법을 찾아보는 브루트포스 문제라고 판단했다.

어차피 숫자 버튼과 +, - 버튼을 섞어서 쓰면 최소로 버튼을 눌러야 하기 때문에 별로 의미가 없다. 따라서 가고자 하는 채널이 주어졌을 때,

-와 +버튼만 눌러서 목표 채널로 가는 방법
어떤 채널로 이동한 뒤에 -와 +버튼을 눌러 목표 채널로 가는 방법

두가지 방법이 있다.

그래서 초기 답 (ans 변수) 을 현재 위치인 100에서 오직 +와 -버튼만을 이용하여 목표 채널로 갈 수 있는 횟수로 설정해 준 뒤에, 1부터 999,999까지 모든 채널을 돌아가면서 해당 채널로 이동한 뒤에, +, -버튼으로 목표 채널로 가는 경우의 버튼을 누르는 횟수를 구해 주고, 기존 ans와 비교해가면서 최솟값을 구해줬다.

이때 버튼이 고장나는 경우가 있을 수 있으므로, can_go() 라는 함수에서 해당 채널을 이루고 있는 숫자들 중에서 고장난 버튼이 없는지를 확인해주었다.

코드

/*
2022-4-1
1107_리모컨
https://www.acmicpc.net/problem/1107
*/

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

int n, m, ans;
bool button[10];

int can_go(int num)
{
	string temp = to_string(num);
	for(int i = 0; i < temp.length(); i++)
	{
		if (button[temp[i] - '0'] == false)
			return (-1);
	}
	return (temp.length());
}

void go()
{
	int temp;
	if (n < 100)
		ans = 100 - n;
	else
		ans = n - 100;
	for(int i = 0; i <= 999999; i++)
	{
		temp = can_go(i);
		if (temp == -1)
			continue;
		if (i < n)
			temp += (n - i);
		else if (i > n)
			temp += (i - n);
		if (temp < ans)
			ans = temp;
	}
}

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

	int input;
	memset(button, true, sizeof(button));
	cin >> n;
	cin >> m;
	if (m != 0)
	{
		for(int i = 0; i < m; i++)
		{
			cin >> input;
			button[input] = false;
		}
	}
	if (n == 100)
	{
		cout << 0;
		return (0);
	}
	go();
	cout << ans;

	return (0);
}

1107. 리모컨

문제

풀이

아이디어

코드