본문 바로가기

백준_BOJ/BOJ (골드)

[백준/알고리즘] 1107번 리모컨 (골드 5)

클릭하면 백준 페이지로 이동합니다.


 

BOJ 1107번

 

수빈이는 현재 TV채널 100번을 보고있다. 리모컨으로 채널을 변경할 수 있는데, 리모컨에는 0부터 9까지 숫자버튼과 +버튼, -버튼이 있다. 리모컨이 일부 고장나서 숫자버튼 중 몇개가 고장난 상태이다.
현재 채널에서 채널 N으로 이동하기 위한 버튼 클릭 횟수를 출력하시오.

 

풀이 알고리즘 : 완전탐색

 

먼저 고장난 숫자버튼을 canuse 배열에 저장해서 해당 버튼을 사용할 수 있는지 확인한다.

 

그리고 채널 N은 최대 500000까지의 정수이다.

 

채널 100에서 채널 N으로 이동하는 방법 중에, N보다 큰 정수에서 -버튼을 계속 눌러서 채널 N으로 이동할 수 있는 경우가 있으므로, 완전탐색의 범위는 1부터 1000000까지 진행한다.

 

각각의 정수에 대해서, move[i]는 채널 i로 바로 이동했을 때 최소 거리이다.

 

채널 i를 이루는 숫자가 모두 사용할 수 있는 경우, 각각의 숫자 버튼을 누르는 횟수와 채널 100번에서 (+, -) 버튼만 이용해서 누른 횟수 중 최솟값으로 정의할 수 있다.

즉, move[i] = min( '채널의 길이', abs(100 - i) )

 

숫자 버튼이 고장나서 채널 i로 이동할 수 없는 경우, move[i]는 채널 100번에서 (+, -) 버튼만 이용해서 누른 횟수로 일단 정의할 수 있다.

즉, move[i] = abs(100 - i)

 

이후 1부터 1000000까지의 정수 i에 대해,

 

채널 100번에서 i번으로 이동 후, i번에서 채널 N번으로 이동하는 경우와, 현재 계산한 경우 두가지 중에 최솟값으로 계속해서 최신화시켜준다.

 

이후 마지막에 move[N]을 출력하면 답이다.

 

구조가 플로이드-와샬 알고리즘처럼, 중간 노드를 거쳐가는 경우가 더 짧으면 그것으로 변경하는 구조와 닮은 문제였다.

 

소스코드 보기

 

더보기
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수
int movei[1000000 + 1];

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	// 초기화
	string n; cin >> n;
	int m; cin >> m;
	bool canUse[10];
	
	memset(canUse, true, sizeof(canUse));
	memset(movei, 0, sizeof(movei));
	for(int i = 0; i < m; i++) {
		int btn; cin >> btn;
		canUse[btn] = false;
	}
	
	// 완전탐색
	for(int i = 0; i < 1000000 + 1; i++) {
		string channel_s = to_string(i);
		bool directMove = true;
		for(int j = 0; j < channel_s.size(); j++) {
			directMove = directMove && canUse[channel_s[j] - '0'];
		}
		if(directMove) {
			movei[i] = min((int)(channel_s.size()), abs(100 - i));
		} else {
			movei[i] = abs(100 - i);
		}
	}

	int minmove = 1000000 + 1;

	// 최소 버튼 클릭횟수 계산
	for(int i = 0; i < 1000000 + 1; i++) {
		int curmove = min(movei[i] + abs(i - stoi(n)), movei[stoi(n)]);
		if(curmove < minmove) {
			minmove = curmove;
		}
	}

	cout << minmove;

	return 0;
}