BOJ 1107. 리모컨
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, + 와 - 가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
1. 문제 해석
이 문제는 100번 채널에서 N번 채널로 이동하는 무수히 많은 방법 중에서 가장 최소의 횟수로 버튼을 누르는 방법을 구하는 문제이다. 예를 들어, 5457이라는 채널에 이동하려면 5, 4, 5, 7을 눌러서 4번만에 이동할 수 있다. 만약, 숫자 버튼 7이 고장났다면, 5, 4, 5, 6, + 또는 5, 4, 5, 8, - 를 눌러 5번 만에 이동할 수 있다. 6, 7, 8이 고장난 경우에는 5, 4, 5, 5, +, + 또는 5, 4, 5, 9, -, -를 눌러 6번만에 이동할 수 있다. 5, 6, 7, 8, 9가 고장난 경우에는 손으로 구하기에는 시간이 너무 오래 걸린다. 즉, 어떤 경우가 최소가 되는지 알기가 어렵다.
이렇게 답을 구하기 위해서 정확한 루트를 찾기 어려운 경우에는 브루트 포스로 해결하는 것이 낫다. 단, 이때 브루트 포스를 실행할 경우에 대한 분류를 정확히 해야한다. 이전의 예시처럼 5457에 이동하고 싶은데, 6, 7, 8이 고장난 경우를 생각해보자. 이 경우에 5, 4, 3, 5, +, +, +, 5, 4, -, -, 5, 4, 5, 5, +, + 는 절대 답이 될 수 없다. 왜냐하면 5, 4, 3, 5, +, +, +, / 5, 4, -, -, / 5, 4, 5, 5, +, + 이렇게 중간에 숫자가 나오는 경우, 앞에서 입력한 버튼은 모두 의미가 없어지기 때문이다. 이 문제는 버튼을 누르는 횟수의 최솟값을 구하는 문제인데, 이처럼 의미없는 방법은 절대 최소가 될 수 없다. 또 다른 오답으로, 5, 4, 5, 5, -, -, +, +, +, + 는 절대 답이 될 수 없다. 왜냐하면 5, 4, 5, 5, -, -, +, +, +, + 버튼을 - 에서 + 로 누르는 순간 이미 이동한 채널을 또 이동하는 중복이 발생하기 때문이다.
- 숫자버튼을 다시 누르는 방법은 절대 최소가 될 수 없다.
- +나- 버튼을 번갈아가며 누르는 방법은 절대 최소가 될 수 없다.
그렇다면 버튼을 누르는 최소의 방법이 되기위한 조건은 다음과 같을 것이다.
- 숫자 버튼을 한번 누르고, 그 다음 +나- 중 하나만 연속해서 눌러야 한다.
- 이동하려고 하는 채널인 N의 범위는 0 ≤ N ≤ 500,000 이다.
최소 경로인 경우는 숫자 버튼을 누르고 +나-중 하나만 연속해서 누르거나 or +나-만 연속해서 눌러서 이동하는 경우가 있을 것이다. 예를 들어, 100에서 시작했을 때 모든 숫자버튼이 고장났다면, 최악의 경우에 N이 500,000이라면 대략 500,000번 +버튼을 눌러야 한다. 그런데 숫자버튼의 고장 유무에 따라서 위쪽에서 아래로 내려오는 경우도 생각해야한다. 1000,000에서 -버튼을 연속해서 눌러 500,000에 도착하는 경우도 있을 수 있다. 따라서 숫자 버튼을 눌러서 이동하는 채널 C도 대략 0 ≤ C ≤ 1000,000 이면 충분하다.
2. 문제 풀이
정답이 되기 위한 조건은 다음과 같다.
- 숫자 버튼을 한번 누르고, 그 다음 +나- 중 하나만 연속해서 눌러야 한다.
- +나- 중 하나만 연속해서 눌러야 한다.
- 이동하려고 하는 채널인 N의 범위는 0 ≤ N ≤ 500,000 이다.
- 숫자 버튼을 눌러서 이동하는 채널 C도 0 ≤ C ≤ 1,000,000 이면 된다.
이러한 조건에 맞추어 정답을 구하기 위해서 크게는 다음과 같은 과정을 따를 것이다.
- 이동할 채널 C를 정한다.
- C에 포함되어있는 숫자 중에 고장난 버튼이 있는지 확인한다.
- 고장난 버튼이 포함되어 있지 않다면 |C - N|을 계산해 +나 - 버튼을 몇 번 눌러야 하는지를
계산한다.
1. 이동할 채널 C를 정한다.
만일 모든 숫자 버튼이 고장나지 않았다면 다음과 같이 C를 모두 이동해 보면서 시작해야 한다.
for (int i=0; i<=1000000; i++) {
int c = i; // 모든 채널로 숫자버튼을 통해 이동
}2. C에 포함되어있는 숫자 중에 고장난 버튼이 있는지 확인한다
숫자 버튼을 통해 이동하려는 채널 C에 고장난 버튼이 있다면 숫자버튼을 통해 이동할 수 없다. 따라서 포함된 숫자 버튼 중에 고장난 버튼이 있는지 확인해 주어야한다. 이것은 아래와 같이 두 가지 방법으로 검사할 수 있다.
- 수를 문자열로 바꾼 다음, 한 글자씩 검사하는 방법
- 수를 10으로 계속해서 나누면서 하나씩 검사하는 방법
bool broken[10]; // 버튼이 고장나 있으면 true, 아니면 false
bool possible(int c) {
while (c > 0) {
if (broken[c % 10]) return false;
c /= 10;
}
return true;
}이렇게 구현하면 possible(0)은 항상 true을 리턴하게 되므로 아래와 같이 0인 경우 예외 처리를 한다.
if (c == 0) { // c가 0인 경우
if (broken[0]) {
return false;
} else {
return true;
}
}possible을 불가능하면 0, 가능하면 버튼을 눌러야 하는 횟수를 리턴하게 변경
int possible(int c) {
if (c == 0) {
return broken[0] ? 0 : 1;
}
int len = 0;
while (c > 0) {
if (broken[c % 10]) return 0;
len += 1;
c /= 10;
}
return len;
}가장 처음에 보고 있는 채널은 100이기 때문에, 초기값을 100에서 숫자 버튼을 누르지 않고 +나- 버튼으로만 이동하는 횟수로 지정한다.
#include <iostream>
using namespace std;
bool broken[10]; // 고장난 버튼 정보를 담을 배열
int possible(int c) { // 채널 c로 이동하는 것이 가능한지 확인하는 함수
if (c == 0) { // 이동할 채널이 0인 경우 예외처리
if (broken[0]) {
return 0;
} else {
return 1;
}
}
int len = 0;
while (c > 0) {
if (broken[c % 10]) { // 고장난 버튼이 있다면 0리턴
return 0;
}
len += 1;
c /= 10;
}
return len;
}
int main() {
int n, m;
cin >> n; cin >> m;
for (int i = 0; i < m; i++) { // 고장난 버튼 정보를 입력받아 저장
int x; cin >> x;
broken[x] = true;
}
int ans = n - 100; // 우선 +나-만으로 이동하는 경우를 정답으로 저장
if (ans < 0) {
ans = -ans;
}
for (int i = 0; i <= 1000000; i++) { // 모든 채널에 대하여 반복
int c = i;
int len = possible(c); // 숫자 버튼으로 이동 가능한지 확인
if (len > 0) { // 0보다 크다면 고장난 숫자 버튼이 포함되지 않은 것 이므로
int press = c - n; // +나- 버튼 누른 횟수 |C-N| 구하기
if (press < 0) {
press = -press;
}
if (ans > len + press) { // 숫자 버튼을 누르지 않고 이동한 것보다 작다면
ans = len + press;
}
}
}
printf("%d\n", ans);
return 0;
}