리모컨(1107번), Gold5
https://www.acmicpc.net/problem/1107
문제풀이
브루트포스 알고리즘으로 풀 수 있는 문제이다.
우선 생각해볼 수 있는 채널 이동 방법은 다음이 있다.
1) 숫자(0-9)버튼을 통해 목표 채널에 도달
2) +/- 버튼을 통해 목표 채널에 도달
3) 숫자 버튼을 이용해 목표 채널에 가까운 채널로 이동 후, +/- 버튼 통해 목표 채널에 도달🤔 채널 이동 방법을 어떻게 구현할까
우선 출력해줄 값인 result 변수를 초기화해주자.
가장 간단하게 구현할 수 있는 방법은 2번(+/-버튼)이다.
int result = Math.abs(N - 100)
+/- 버튼은 각 +1/-1씩 이동한다. 따라서 목표값에서 현재 위치한 값을 빼주면 +/- 버튼 눌러야 하는 횟수를 알 수 있다.
이때 목표 채널이 현재 채널(100번)보다 작을 수 있으므로 절대값으로 변환해주는 것을 잊지 말자.
다음은 숫자 버튼을 이용하여 목표 채널에 도달하는 방법을 구현해보자.
목표 채널의 최댓값은 500,000 이지만 실제로 버튼은 0부터 9까지 존재하기 때문에 누를 수 있는 채널은 999,999까지 있다.
우리의 문제 풀이 접근 방식은 브루트포스이기 때문에 모든 경우를 고려해 줘야 한다.
완전탐색답게 0부터 999,999까지 반복문을 반복하여 탐색한다.
🤔 고장난 버튼과 가까운 채널을 찾는 방법
모든 숫자 버튼을 탐색하면서 동시에 3번 방법(가까운 채널 탐색 후, +/- 버튼으로 목표 채널 도달)도 구현해보자.
먼저 현재 탐색 중인 채널을 String 변수로 받아서 임시로 정의한다.
그리고 중간에 반복문을 빠져나가야 하는지 판단할 boolean형 변수 isBreak도 선언해준다.
우리는 모든 채널을 탐색하면서 다음을 확인해야 한다.
1) 현재 탐색 중인 채널에 고장난 숫자 버튼이 포함되어 있는 경우
2) 현재 탐색 중인 채널로 이동 가능한 경우(고장난 버튼이 없음)만약 전자와 같다면 우리는 해당 채널로 이동할 수 없기 때문에 isBreak를 true 값으로 변환하고 반복문을 빠져나와 다음의 채널을 탐색해야 한다.
후자라면 현재 탐색 중인 채널이 목표 채널과 가까운 채널임을 확인하고 결과를 설정해야 한다.
방법은 임의의 변수 min에 현재 탐색 중인 채널로 이동하기 위해 눌러야 하는 횟수를 저장해주고, 미리 선언된 result 변수와 비교하여 둘 중 최솟값으로 result 값을 변경해주면 된다.
- 임의 변수 min 설정(현재 탐색 중인 채널로 이동하기 위해 버튼을 누르는 횟수)
int min = len + Math.abs(N - i)
len은 현재 탐색 중인 채널의 길이로 만약 두 자릿수라면 두 번 눌러줘야 한다는 것을 의미한다. 그런 다음 +/-로 목표 채널에 도달하기 위해 버튼을 눌러줘야 하기 때문에 다음과 같은 식이 성립된다.
- 미리 선언된 result값과 비교, 둘 중 더 작은 값으로 result 변수 변경
result = Math.min(result, min)
Math클래스의 min함수를 이용해 현재 채널에서의 이동 횟수와 result로 저장된 이동 횟수 중 더 작은 값으로 result 변수를 업데이트해준다.
0부터 999,999까지 위의 과정을 반복해가며 result값을 업데이트해주는 것이다.
소스코드
public class BOJ1107 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
boolean[] broken = new boolean[10];
// 고장난 버튼이 0개일 경우 입력 skip 처리 -> NP 방지
if (M != 0) {
String[] input = br.readLine().split(" ");
for(int i = 0; i < M; i++)
broken[Integer.parseInt(input[i])] = true;
}
br.close();
int result = Math.abs(N - 100); // 2번 방법으로 초기화
// 고장나지 않은 리모콘 버튼으로만 N과 가장 근사한 번호를 만든 후 +, - 로 이동하는 값 중의 최소값을 선택
for(int i = 0; i <= 999999; i++) {
String str = String.valueOf(i);
int len = str.length();
boolean isBreak = false;
for(int j = 0; j < len; j++) {
if(broken[str.charAt(j) - '0']) {
isBreak = true;
break;
}
}
if(!isBreak) {
int min = len + Math.abs(N - i);
result = Math.min(min, result);
}
}
System.out.println(result);
}
}후기
가장 간단하고 무식한 방법이지만 브루트포스 알고리즘 문제는 많이 풀어보지 않아서 접근 방법을 모색하기가 어려웠다.
최대값인 500,000에 속아서 999,999까지 탐색하는 것을 놓치냐 안 놓치냐가 풀이의 관건인 듯 하다.
그 뒤에도 고장난 채널을 처리하는 방법, 현재 탐색 중인 채널의 길이까지 고려하여 이동 횟수를 구하는 법 등 고려사항들이 많은 문제였다.
괜히 골드가 아니다... 언제쯤 세세한 조건들을 꼼꼼하게 챙기며 구현할 수 있을까!
