BOJ 1107. 리모컨

🙇‍♀️[Gold V] 리모컨 - 1107

문제 링크

성능 요약

메모리: 2020 KB, 시간: 288 ms

분류

브루트포스 알고리즘

제출 일자

2024년 1월 18일 15:38:06

문제 설명

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

🚀풀이

완전 탐색 문제로 나는 DFS를 이용했다.

예외처리가 중요한 문제였는데 특히 한자리 숫자인 0일때 잘 처리했어야했다.

대략적인 틀은 금방 잡고 풀었는데 반례가 많아서 계속 틀렸다.

DFS는 다음과 같이 짰다.

void DFS(int L, int ret)
{
	if (L > digit + 1)
		return;

	if (L == digit || L == digit - 1 || L == digit + 1)
	{
		if (L != 0)
		{
			int dis = abs(ret - num);
			int temp = dis + L;
			//cout << "ret : " << ret << endl;
			res = min(res, temp);
			//cout << "res : " << res << endl;

            // 원하는 숫자가 0일때 예외처리
			if (digit == 1 && ret == 0 && num == 0)
				res = 1;
		}
	}


	for (int i = 0; i <= 9; ++i)
	{
		bool flag = true;
		for (int j = 0; j < broken.size(); ++j)
		{
			if (i == broken[j])
			{
				flag = false;
				break;
			}
		}

		if (flag == true)
		{
			DFS(L + 1, ret * 10 + i);
		}
	}
}

고장난 숫자를 제외하고 모든 번호를 눌러봤다.

중요한 점은 원하는 숫자의 자릿수까지 누르는게 아니라 그전, 그후 까지 생각해서 경우를 다 생각해야한다.

또한 +,-로만 원하는 숫자까지 가는 경우가 더 짧을 수 있으므로 DFS가 끝나고 마지막에 따로 처리해서 최소값을 구해야한다.

겨우 풀었다…

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int num, n, digit = 0, cur = 100, res = 123456789;
vector<int> broken;
void setting()
{
	cin >> num >> n;
	broken = vector<int>(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> broken[i];
	}

	int temp = num;
	while (temp > 0)
	{
		digit++;
		temp /= 10;
	}

	if (num == 0)
		digit = 1;
}

void DFS(int L, int ret)
{
	if (L > digit + 1)
		return;

	if (L == digit || L == digit - 1 || L == digit + 1)
	{
		if (L != 0)
		{
			int dis = abs(ret - num);
			int temp = dis + L;
			//cout << "ret : " << ret << endl;
			res = min(res, temp);
			//cout << "res : " << res << endl;

			if (digit == 1 && ret == 0 && num == 0)
				res = 1;
		}
	}


	for (int i = 0; i <= 9; ++i)
	{
		bool flag = true;
		for (int j = 0; j < broken.size(); ++j)
		{
			if (i == broken[j])
			{
				flag = false;
				break;
			}
		}

		if (flag == true)
		{
			DFS(L + 1, ret * 10 + i);
		}
	}
}

void solve()
{
	DFS(0, 0);

	int temp = abs(num - cur);
	res = min(res, temp);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}