백준 1107 - 리모컨 (C++)

 

 

리모컨에는 0~9까지의 숫자 버튼이 있고, +와 -의 버튼이 있다.

 

숫자를 직접 눌러서, 원하는 채널로 옮길 수도 있고 +와 -버튼을 이용하여 원하는 채널로 이동할 수도 있다.

 

하지만, 리모컨에는 모든 숫자가 작동하는 것이 아니라 고장난 숫자가 있을 수도 있다.

그렇기 때문에, 항상 숫자를 직접 눌러서 채널을 옮길 수는 없다.

(원하는 채널이 134채널인데, 1번 3번 4번 숫자패드가 고장났다면 숫자를 눌러서 134번으로 이동할 수는 없다.)

 

이 때, 멀쩡한 숫자 버튼와 +, -버튼을 이용해서 원하는 채널에 접근하기 위해 버튼을 누르는 횟수의 최소값을 구하자.

 

 

문제 풀이

 

이 문제는 다소 무식한 방법으로 풀었다.

좀 유식해보이게 말하고 싶다면, 브루트 포스라고 하기도 한다.

 

먼저, 원하는 채널에 접근하기 위해 떠올리기 가장 쉬운 아이디어는 숫자버튼으로 원하는 채널에 최대한 근접하게 이동한 다음, +와 -를 눌러서 해당 채널까지 이동하는 것이다.

 

그렇다면, 숫자버튼으로 누를 수 있는 채널중에 원하는 채널과 가장 가까운 채널을 찾아야 하는데 어떻게 찾을까?

 

위에서 말한 아이디어는 아래와 같다.

  위의 그림에서, 하늘색 네모칸은 숫자 버튼을 눌러서 이동할 수 있는 채널들이다.

그 중에서, 가장 가까운 채널으로 숫자 버튼을 눌러 이동한 후에, +,- 버튼으로 한칸씩 움직이며 원하는 채널에 도달하는 것이다.

 

이를 반대로 생각해보자.

 

원하는 채널에서, +, - 버튼을 이용해 1씩 채널을 옮기며 탐색하다보면, 숫자버튼을 눌러서 이동할 수 있는 채널을 찾을 수 있지 않을까?

 

누를 수 있는 숫자가 (1, 4, 6)이고 이동하고자 채널이 150이라고 해보자.

 

150에서 1을 빼면, 149가 된다. 이 149는 숫자를 눌러서 이동할 수 있을까? 9 버튼이 망가졌으므로 이동할 수 없다.

다시 149에서 1을 빼면, 148이 된다. 148또한 숫자를 눌러서 이동할 수 없다.

반복하다 보면, 146이라는 채널은 숫자 버튼을 눌러서 이동할 수 있음을 확인할 수 있다.

 

하지만, 빼기만 검사해서는 안된다.

 

누를 수 있는 숫자가, (2, 3, 4) 이고, 현재 채널이 200이라면 이 때, 숫자 번호로 누를 수 있는 가장 가까운 번호는 222이다. 즉, 위의 방식으로 빼기만 검사했다간 이 채널을 탐색할 수 없게 된다.

 

그러므로, 이동하고자 하는 채널에서 1씩 빼며 가까운 채널을 탐색하는 경우와

1씩 더해가며 채널을 탐색하는 경우를 둘 다 구해야 한다.

 

두 경우에서 버튼을 몇 번 누르는지 비교한 후 더 적게 누르는 쪽을 답으로 출력하면 된다.

하지만, 사실 이렇게만 출력하면 문제를 맞추지 못한다.

 

왜냐하면, 한 가지 경우의 수가 더 있기 때문이다.

 

누를 수 있는 버튼이, (2) 이고 이동하고자 하는 채널이 101 이라고 해보자

이 때, 숫자 버튼으로 이동할 수 있는 채널중 가장 가까운 채널은 22이다.

22를 눌렀다가 +버튼을 89번 눌러서 101일번 채널에 도착할 수 있다.

이 경우엔 총 91번의 버튼을 눌러야 한다.

 

하지만, 이렇게 하지 않고 처음에 +버튼 하나만 누른다면?

100채널에서 101채널로 단 1회만에 이동할 수 있다.

 

즉, 숫자 버튼을 사용하지 않고 +버튼 (혹은 -버튼) 만을 사용해서 원하는 채널에 도달하는 경우도 고려해야 한다는 것이다.

 

문제의 답은 아래 3가지의 경우 중 버튼을 누르는 횟수가 가장 적은 것을 출력하면 된다.

 

1. 이동하고자 하는 채널에서 1씩 빼며, 숫자 버튼을 눌러 이동할 수 있는 가장 가까운 채널을 탐색하는 경우

2. 이동하고자 하는 채널에서 1씩 더하며, 숫자 버튼을 눌러 이동할 수 있는 가장 가까운 채널을 탐색하는 경우

3. +버튼 (혹은 -버튼)만을 눌러서 이동하고자 하는 채널에 도달하는 경우

 

 

풀이 코드

 

int TargetChannel = 0;
std::cin >> TargetChannel;

int NumOfBrokenBt = 0;
std::cin >> NumOfBrokenBt;

std::vector<bool> PushableBts(10, true);

if (NumOfBrokenBt > 0)
{
    for (int i = 0; i < NumOfBrokenBt; i++)
    {
        int Bt = 0;
        std::cin >> Bt;

        PushableBts[Bt] = false;
    }
}

 

먼저, 위와 같이 입력을 받아주었다.

이동하고자 하는 채널을 입력받았고, 부서진 버튼의 개수를 입력받았다.

 

이후, bool값을 저장하는 벡터를 숫자버튼 개수만큼 resize하였고, 초기값을 모두 true로 저장하였다.

이 벡터에서 1번 인덱스의 값이 true라면, 1번 숫자 버튼은 누를 수 있다는 의미이다. 반대로, 2번 인덱스의 값이 false라면2번 숫자 버튼은 망가졌다는 의미이다.

 

이후, 부서진 버튼의 개수가 1개 이상이라면, 입력에 따라 배열의 값을 false로 바꿔주면서 망가진 숫자 버튼을 표현해주었다.

 

다음은 숫자버튼으로 가장 가까운 채널로 이동한 뒤, +,-로 원하는 채널에 도달할 때 버튼을 몇 번 눌러야 하는가를 구하는 함수이다.

int GetCount(const std::vector<bool>& _PushableBts, int _TargetChannel, int _AddValue)
{
	int CurChannel = _TargetChannel;
	int Count = 0;

	while (true)
	{
		if (CurChannel > 1000000 || CurChannel < 0)
		{
			Count = INT_MAX;
			break;
		}

		if (CurChannel == 100)
		{
			break;
		}

		bool CanNot = false;
		std::string ChannelStr = std::to_string(CurChannel);
		for (int i = 0; i < ChannelStr.size(); i++)
		{
			int CurNum = ChannelStr[i] - '0';

			if (_PushableBts[CurNum] == false)
			{
				CanNot = true;
				break;
			}
		}

		if (CanNot == false)
		{
			Count += ChannelStr.size();
			break;
		}

		Count++;
		CurChannel += _AddValue;
	}

	return Count;
}

 

인자중에 첫 번째 인자는 숫자 버튼 배열이다. 두 번째 인자는 이동하고자 하는 채널의 번호이며, 3번은 더하며 탐색할것인가 빼며 탐색할 것인가를 설정하는 것이다.

 

함수 내부에서 선언된 Count는 버튼을 몇 번 눌렀는가 이다.

 

반복문 내부를 보면, 가장 위에 조건문이 하나 있다.

if (CurChannel > 1000000 || CurChannel < 0)
{
    Count = INT_MAX;
    break;
}

이 조건은, 가장 가까운 채널을 탐색하지 못하였을 경우에 대한 예외처리이다.

채널은 음수가 될 수 없고, 1000000을 넘을 수도 없다.

(물론 실제로는 100만을 넘을 수는 있는데, 그 범위를 고려할 이유가 없다.)

 

아무튼 가장 가까운 채널을 탐색하지 못했다면, INT_MAX를 반환해주어 답이 되지 못하도록 설정해주었다.

(최소값을 기준으로 답을 출력하기 때문에, INT_MAX가 출력될 일은 없기 때문이다.)

 

다음 부분을 보자.

bool CanNot = false;
std::string ChannelStr = std::to_string(CurChannel);

for (int i = 0; i < ChannelStr.size(); i++)
{
    int CurNum = ChannelStr[i] - '0';

    if (_PushableBts[CurNum] == false)
    {
        CanNot = true;
        break;
    }
}

 

ChannelStr은 각 자리수의 숫자를 좀 더 편하게 탐색하기 위해 int형의 채널을 string으로 변환해준 것이다.

모든 자리수의 숫자를 검사하면서, 숫자 패드로 누를 수 없는 번호가 섞여있는지 검사하고 있다.

 

만약, 모든 번호를 누를 수 있다면, 반복문이 끝나고 나서 CanNot은 false일 것이고, 단 하나라도 누를 수 없다면 CanNot은 true가 될 것이다.

 

if (CanNot == false)
{
    Count += ChannelStr.size();
    break;
}

 

CanNot이 false라면 (해당 채널을 숫자 번호를 눌러 이동할 수 있다면)

해달 채널의 길이를 Count에 더해준 뒤 문자열을 종료해주고 있다.

해당 채널이 1313이라면, 총 4번의 버튼을 눌러야 하기 때문에 문자열의 길이를 더해준 것이다.

 

Count++;
CurChannel += _AddValue;

만약, CanNot이 true라서 반복문이 끝나지 않았다면, Count를 1회 더해주고, 채널을 1씩 더해주거나 빼주면서 다음 채널을 탐색하게 될 것이다.

 

(_AddValue는 함수의 파라미터에 등록된 변수인데, 인수로 1을 전달하면 1씩 더하며 탐색할 것이고 -1을 전달하면 1씩 빼며 탐색할 것이다.)

 

위의 함수를 아래와 같이, 두 번 실행해준다.

int SubCount = 0;
int AddCount = 0;

SubCount = GetCount(PushableBts, TargetChannel, -1);
AddCount = GetCount(PushableBts, TargetChannel, 1);

 

SubCount는 1씩 빼며 채널을 탐색한 것이고, AddCount는 1씩 더하며 채널을 탐색한 것이다.

 

int OnlyPMCount = abs(TargetChannel - 100);

OnlyPMCount는 +, - 만을 이용하여 채널을 이동했을 때 버튼을 누른 횟수이다.

그냥, 원하는 채널에서 현재 채널을 뺴주면 된다.

단, 음수가 나올 수도 있기 때문에 절대값을 취해주었다.

 

마지막으로 아래와 같이 최소값을 구한 뒤 출력해주면 끝이다.

int Answer = 0;

Answer = std::min(SubCount, AddCount);
Answer = std::min(Answer, OnlyPMCount);

std::cout << Answer;

return 0;

 

 

코드 전문

 

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <climits>

void Init()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
}

int GetCount(const std::vector<bool>& _PushableBts, int _TargetChannel, int _AddValue)
{
	int CurChannel = _TargetChannel;
	int Count = 0;

	while (true)
	{
		if (CurChannel > 1000000 || CurChannel < 0)
		{
			Count = INT_MAX;
			break;
		}

		bool CanNot = false;
		std::string ChannelStr = std::to_string(CurChannel);
		for (int i = 0; i < ChannelStr.size(); i++)
		{
			int CurNum = ChannelStr[i] - '0';

			if (_PushableBts[CurNum] == false)
			{
				CanNot = true;
				break;
			}
		}

		if (CanNot == false)
		{
			Count += ChannelStr.size();
			break;
		}

		Count++;
		CurChannel += _AddValue;
	}

	return Count;
}

int main()
{
	Init();

	int TargetChannel = 0;
	std::cin >> TargetChannel;

	int NumOfBrokenBt = 0;
	std::cin >> NumOfBrokenBt;

	std::vector<bool> PushableBts(10, true);

	if (NumOfBrokenBt > 0)
	{
		for (int i = 0; i < NumOfBrokenBt; i++)
		{
			int Bt = 0;
			std::cin >> Bt;

			PushableBts[Bt] = false;
		}
	}

	int SubCount = 0;
	int AddCount = 0;

	SubCount = GetCount(PushableBts, TargetChannel, -1);
	AddCount = GetCount(PushableBts, TargetChannel, 1);

	int OnlyPMCount = abs(TargetChannel - 100);
	
	int Answer = 0;
	Answer = std::min(SubCount, AddCount);
	Answer = std::min(Answer, OnlyPMCount);

	std::cout << Answer;

	return 0;
}