문제
https://www.acmicpc.net/problem/1107
풀이
- 리모컨 버튼을 너무 세게 누르는 바람에 일부 숫자 버튼이 고장 남
- 리모컨에는 0부터 9까지 숫자,
+와-버튼이 있다. - 채널 0에서
-를 누른 경우에는 채널이 변하지 않고 채널은 무한대 만큼 존재 - 채널
N으로 이동하려고 한다. - 어떤 버튼이 고장났는지 주어졌을 때, 채널
N으로 이동하기 위해 눌러야 하는 버튼의 최솟값 출력
어떤 규칙이 있을까 찾아보려 했지만, 실패했습니다.
브루트 포스를 이용해 풀어봤습니다.
우선 누를 수 있는 버튼을 0부터 최대 100만까지 다 눌러봤습니다.
그 중에서 최솟값을 찾아내는 방식으로 해봤습니다.
예제 1번을 같이 봐봅시다.
우리는 5457번으로 이동을 할 것입니다.
그런데 번호 6, 7, 8이 고장이 났습니다.
이 말은 즉슨, 545까지는 누를 수 있으나 7을 누르지 못해 다른 번호를 누르고 + 버튼이나 - 버튼을 눌러 채널을 변경해야 하죠
이 번호에서의 최솟값은 5455를 누르고 + 버튼을 2번 누르거나, 5459에서 -버튼을 2번 누르는 것입니다.
즉 !! 고장난 버튼을 누르지 않고 이동하려는 채널의 글자 길이만큼 누르고(4번) +나 - 버튼을 누르는 행위를 해야 하죠
이 예제에서는 5455나 5459가 그 4글자에 해당합니다.
을 하게 되면 우리가 눌러야 하는 최소 버튼 클릭 수인 6을 구할 수 있습니다.
위 아이디어를 갖고 문제를 풀어봅시다.
// 고장난 버튼 배열
broken = new boolean[10];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
broken[Integer.parseInt(st.nextToken())] = true;
}- 고장난 버튼은
boolean배열로 선언해 주었습니다.
// 브루트 포스
for (int i = 0; i <= 1000000; i++) {
String target = String.valueOf(i); // i를 문자열로 변환
boolean flag = true; // 현재 문자열에서 고장난 버튼이 존재하는지 판별하는 변수
for (int j = 0; j < target.length(); j++) {
if (broken[target.charAt(j) - '0']) { // 현재 채널의 문자열 중 고장난 버튼을 눌러야 하는 경우가 있다면
flag = false; // false 후 종료
break;
}
}
if (flag) { // 전부 버튼을 누를 수 있다면
int cost = target.length() + Math.abs(i - n); // 문자열의 길이 + (현재 채널 - 찾으려는 채널)
if (answer > cost) answer = cost; // 최솟값 갱신
}
}- 여기가 핵심입니다.
- 경유하려고 하는 채널
i를 문자열로 변환 i의 문자열을 돌면서 고장난 버튼이 있는지 판별- 고장난 버튼이 있다? =>
i+1탐색 - 고장난 버튼이 없다? => 현재
i의 길이 + (i - n)의 절댓값을 눌러야 하는 횟수로 찾아냅니다.- 후에 최솟값을 비교해 갱신합니다.
여기까지만 하면 아마 96퍼에서 오류가 발생할 겁니다. (맞왜틀?)
문제를 꼼꼼히 읽으셨거나 입력 예제 5번을 확인하신 분은 눈치 채셨을텐데, m이 0인 경우도 있습니다 !! 🤯
그래서 m == 0 경우도 쳐줘야 합니다.
if (m == 0) {
// 글자 길이 vs 100(현재 채널) + 버튼 or - 버튼
answer = Math.min(String.valueOf(n).length(), Math.abs(n - 100));
System.out.println(answer);
return;
}answer의 값은- 자릿수대로 누르는 것과
+or-버튼을 누르는 경우를 비교해야 합니다.
(100번 근처인 경우도 있으므로)
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, answer;
static boolean[] broken;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
// 고장난 버튼이 없을 경우
if (m == 0) {
// 글자 길이 vs 100(현재 채널) + 버튼 or - 버튼
answer = Math.min(String.valueOf(n).length(), Math.abs(n - 100));
System.out.println(answer);
return;
}
// 고장난 버튼 배열
broken = new boolean[10];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
broken[Integer.parseInt(st.nextToken())] = true;
}
// 이동해야하는 횟수
answer = Math.abs(n - 100);
// 틀려는 채널이 100번일 경우 바로 출력
if (answer == 0) {
System.out.println(answer);
return;
}
// 브루트 포스
for (int i = 0; i <= 1000000; i++) {
String target = String.valueOf(i); // i를 문자열로 변환
boolean flag = true; // 현재 문자열에서 고장난 버튼이 존재하는지 판별하는 변수
for (int j = 0; j < target.length(); j++) {
if (broken[target.charAt(j) - '0']) { // 현재 채널의 문자열 중 고장난 버튼을 눌러야 하는 경우가 있다면
flag = false; // false 후 종료
break;
}
}
if (flag) { // 전부 버튼을 누를 수 있다면
int cost = target.length() + Math.abs(i - n); // 문자열의 길이 + (현재 채널 - 찾으려는 채널)
if (answer > cost) answer = cost; // 최솟값 갱신
}
}
System.out.println(answer);
}
}