백준 1107 (리모컨) c++

문제

1107번: 리모컨

현재 채널은 100번입니다. 여기서 n번의 채널로 이동하려 할떄 최소로 버튼을 누르는 횟수를 구하는 문제입니다.

여기서 m개의 고장난 번호가 주어지는 데 고장난 번호는 누를 수 없습니다. 

만약 고장난 번호로 이동하려면 '+' 번호나 '-' 를 눌러 +1 또는 -1로 이동가능합니다.

예를 들어 n = 5457 이고 3개의 고장난 번호는 6, 7, 8 이라면 

처음에 5455 총 4번의 버튼을 눌러 5455번 채널로 이동해 + 버튼을 2번 눌러 5457번으로 이동 가능합니다.

 

여기서 제가 찾아낸 단서는

1) 일단 고장나지 않은 번호를 사용해 n과 최대한으로 가까이 만들어야 합니다.

그 다음 '+' 나 '-' 둘중 하나를 선택해 n을 만들어야 합니다.

2) 100번 부터 시작하므로 abs(n - 100) 과 1)과 비교해야 합니다.

 

bruteforce를 진행합니다.

for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		chk[a] = true;
	}

먼저 chk 배열을 통해 고장난 번호를 체크해 줍니다.

int result = abs(n - 100);

result 변수에는 100번 부터 시작해 n번까지 누르는 횟수 입니다.

예를 들어 n이 101이면 '+' 버튼 1번만 누르면 됩니다.

마지막에 비교해줄것입니다.

for (int i = 0; i <= 1000000; i++) {
	int ans = i;
	int len = check(ans);
	if (len > 0) {
		int button = abs(ans - n);
		result = min(result, button + len);
	}
}
cout << result;

i가 0부터 1000000까지 체크하는데 문제에서 주어진 n의 범위는 50만입니다. 

만약 m이 10이고 모든 번호가 망가졌다면 1000000부터 체크를 해줘야 하므로 반복문을 1000000까지 진행합니다.

len에는 1) 에 해당하는 버튼 횟수가 들어갑니다. 즉, n번까지 가장 가깝게 버튼을 눌러주는 것입니다.

check 함수가 이를 수행합니다.

마지막에 result 변수에 result와 1)을 비교해 넣어줍니다.

int check(int n) {
	if (n == 0) {
		if (chk[0])
			return 0;
		else return 1;
	}
	int len = 0;
	while (n > 0) {
		if (chk[n % 10])return 0;
		n /= 10;
		len++;
	}
	return len;
}

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool chk[10];
int check(int n);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        chk[a] = true;
    }
    int result = abs(n - 100);
 
    for (int i = 0; i <= 1000000; i++) {
        int ans = i;
        int len = check(ans);
        if (len > 0) {
            int button = abs(ans - n);
            result = min(result, button + len);
        }
    }
    cout << result;
 
    return 0;
}
int check(int n) {
    if (n == 0) {
        if (chk[0])
            return 0;
        else return 1;
    }
    int len = 0;
    while (n > 0) {
        if (chk[n % 10])return 0;
        n /= 10;
        len++;
    }
    return len;
}