링크
https://www.acmicpc.net/problem/1107
문제 설명
(정답률 23.109%)
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
입력 예제
5457
3
6 7 8
출력 예제
6
정답 코드
이동하려고 하는 채널 N의 최대값은 500,000 이므로
이동하기 전 고장난 버튼을 이용한 가능한 채널의 범위는 0~999,999이다.
우선 버튼을 이용하지 않을 때와 할 때를 구분한다.
버튼을 이용하지 않을 때는 (+/-만 사용할 때)
기본 채널인 100과 N의 차이의 절대값이다.
그리고
버튼을 이용할 때는 모든 경우를 고려해야 하므로
0~999,999을 반복하면서
고장난 버튼을 이용하지 않을 때를 체크하여
N과의 차이의 절대값(+/- 카운트), 버튼 입력을 카운트를 더한다.
두 경우에서 최솟값을 구한다.
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
Scanner sc = new Scanner(System.in);
int inputNumber = sc.nextInt();
int m = sc.nextInt();
int answer = Integer.MAX_VALUE;
//고장난 버튼의 ArrayList 생성
List<String> brokenRemoteControl = new ArrayList<>();
for (int i = 0; i < m; i++) {
brokenRemoteControl.add(sc.next());
}
//버튼을 입력하지 않는 경우
//현 채널(100)에서 목표 채널까지 +/- 이동 카운트
int noInput = Math.abs(inputNumber - 100);
//0부터 고장난 버튼으로 누를수 있는 최대 값(999,999)까지 반복
for (int i = 0; i <= 999999; i++) {
boolean isBroken = false;
String str = String.valueOf(i);
int length = str.length();
//i가 고장난 버튼을 포함할 경우
for (String s : brokenRemoteControl) {
if (str.contains(s)) {
isBroken = true;
break;
}
}
//i가 고장난 버튼을 포함하지 않을 경우
if (!isBroken) {
//i에서 목표 채널로 +/- 이동할 경우와
//i 입력 카운트
int inputButton = Math.abs(inputNumber - i) + length;
//버튼을 입력하는 경우와 입력하지 않았을 경우 중 최소값이 정답
int min = Math.min(noInput, inputButton);
if (answer > min) {
answer = min;
}
}
}
//모든 버튼이 고장났을 경우는
//버튼을 입력하지 않는 경우이다
if (brokenRemoteControl.size() == 10) {
System.out.println(noInput);
} else {
System.out.println(answer);
}
}
}정리
이 문제는 브루트 포스 문제이므로 전체 경우를 다 따져봐야 한다.
하지만 처음 풀 때는 고장난 버튼의 케이스를 제외하고 채널 N과 비교하여 최솟값인 채널을 구하려고 했었다.
생각만 했을 때는 쉬울거 같았으나 막상 구현을 하려니 몇 시간이 걸려도 하지 못하였다.
그래서 힌트를 찾아봤고 0~999,999의 경우를 체크하는, 브루트 포스에 맞게 푸는 것이였다.
계속 보다보니 지금은 코드가 와닿지만 처음에는 봐도 봐도 이해가 안되길래 고생을 했다.
다른 사람의 풀이를 보니 아래와 같이 재귀적으로 최솟값을 구하던데
나는 직관적으로 와닿지가 않아 코드가 몇 줄 더 추가되더라도 내가 알아보기 쉽게 최솟값을 구했다.
int answer = Math.abs(N - 100);
int min = Math.abs(inputNumber - i) + length;
answer = Math.min(answer, min);