백준 1107 - 리모컨 - 다이나믹 프로그래밍 & 브루트포스

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

1107번: 리모컨

문제

 

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

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

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

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

입력

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

출력

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

 

 

 

문제 풀이

 

---

1. 채널을 있는 그대로 누를 수있다면 가장 적은 횟수로 리모컨을 누를 수 있을 것입니다. (일단 100 근처의 숫자는 생각하지 말아봅시다.)

   예를들어 ,  4.5.7 을 누를 수 있다면 5457 채널에 도달하려면 4번이 최소누르는 횟수일 것이겠죠.

 

2. 직접 누를 수 있는 채널이 있는가 하면, 누를 수 없는 채널도 있습니다. 리모콘이 고장났기 떄문이죠. 이 경우에는 가장 가까운 채널로 이동한다음, +또는 -를 통해서 이동해주어야 합니다.

 

3. 1,2번을 통해서 생각할 수 있는 것은, 눌러서 만들 수 있는 채널 숫자에 대해 메모이제이션을 한 다음, 원하는 채널 N에 접근하기 위해서 추가적으로 필요한 '+' 혹은 '-'의 수를 더해주면 될 것이라는 점입니다. 

 

4. 100근처의 숫자는 조금 예외일 수 있습니다. 99의 경우, 직접 숫자를 누른다면 2번이지만 100에서 -1을 하면 1번만 눌러도 되기 떄문입니다. 

 

 

따라서,  생각하게 된 풀이는 다음과 같습니다. 

• 누를 수 있는 숫자 조합에 대해 메모이제이션을 해둔다.  저장하는 값은 눌러야 하는 횟수 즉 자릿수이다.
  
  • 구현 : 각 누를 수 있는 숫자들에 대해 백트레킹으로 구성한다음, 해당 수의 자릿수를 배열에 저장합니다. (코드에서 DFS 함수, dp 배열 참고)
• '+' 버튼을 통해서 더 적은 횟수로 접근가능한 경우를 업데이트 해준다. (101은 3이 아니라 100에서 1이동한 1번이 더 적은 횟수입니다. 이러한 경우들을 각 저장해둔 채널에 대해 업데이트합니다.)
  • dp[i] = min(dp[i], dp[i-1] + 1) ( 1<= i <= N)
• '-' 버튼을 눌러서 더 적은 횟수로 접근 가능한 경우를 업데이트 해준다.  (99는 2가 아니라 100에서 1이동한 1번이 더 적은 횟수입니다. 이러한 경우들을 업데이트합니다. )
  • dp[i] = min(dp[i] , dp[i+1] + 1) ( N <= i <= biggerNumber)
• 수의 범위는  '+'의 경우 N 이하일때까지, '-'의 경우 N보다 더 큰 수 중 누를 수 있는 숫자조합에서부터 출발합니다. (코드 상에서 biggerNumber)

 

주의사항 :

• 계속 최솟값으로 업데이트를 하기 때문에 배열의 값을 INF 로 초기화하는 것이 필수적입니다. 다만,  INT_MAX 값으로 초기화한다면 오버플로우가 발생가능하므로, 적당히 큰 수를 INF로 설정해두어야 합니다. 
  • 자릿수로써 가질 수 없는 값이므로, 100 정도만 해도 충분합니다. 저 같은 경우 198765432를 사용했습니다.
• 메모이제이션하려는 배열 dp의 크기를 N의 제한에 맞추어서 할당해주면 안되고, 더 큰 값으로 할당해주어야 합니다 
  • N >= 500000 이기 때문에 , dp 도 그에 맞추어서 500001 정도로 할당해준다고 가정해봅시다. 
  • 리모컨에서 0,2,4,6,7,8,9 가 고장난 경우,(즉 1, 5만 사용가능한 경우) 511111에서 '-'를 누르는 것이 가장 적은 횟수의 입력이 될 것입니다. 
  • 즉, 극단적으로 생각해보았을 때 '9'만입력가능한 경우도 고려해야 하므로, '1000,000' 까지 할당해준다면 충분할 것입니다. 

 

 

해결 코드 (C++)

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <sstream>
using namespace std;
#define FAST std::ios::sync_with_stdio(0); std::cin.tie(0);
#define INF 198765432
int N;
int dp[1000010] = {0,};
int cannotUse[11] = {0,};
vector<int> validNumber;


int countDecimal(long long number){
	long long copy = number;
	if(number == 0)
		return 1;
	int cnt = 0;
	while(copy > 0){
		copy /= 10;
		cnt++;
	}
	return cnt;
}

void DFS(long long number) {
	if (number >= 1000001)
		return;
	
	if (dp[number] != INF)
		return;
		
	dp[number] = countDecimal(number);

	for(int i = 0; i < validNumber.size(); i++){
		long long temp = number * 10 + validNumber[i];
		DFS(temp);
	}
}

int main() {
	cin >> N;
	int n;
	
	cin >> n;
	int a;
	for (int i = 0; i < n; i++){
		cin >> a;
		cannotUse[a] = 1;
	}
	
	for (int i = 0; i <= 9; i++) {
		if(cannotUse[i] == 0)
			validNumber.push_back(i);
	}

	for (int i = 0; i <= 1000001; i++)
		dp[i] = INF;	



	//solution
	for(int i = 0; i < validNumber.size(); i++)	{
		DFS(validNumber[i]);
	}

	
	int plusDistance = 0;
	int biggerNumber = 0;
	while(true) {
		if(dp[N + plusDistance] != INF || N + plusDistance > 1000000){
			biggerNumber = plusDistance + N;
			break;
		}
		plusDistance++;		
	}

	dp[100] = 0;
	for(int i = 1; i <= N; i++) {
		dp[i] = min(dp[i-1] + 1, dp[i]);
	}

	for(int i = biggerNumber; i >= N; i--) {
		dp[i] = min(dp[i], dp[i+1] + 1);
	}
	cout << dp[N] << "\n";

}