https://www.acmicpc.net/problem/1107
리모컨 - 완전탐색
완전탐색 문제였다.
입력받은 찾아가야할 채널에서 만들 수 있는 가장 가까운 수를 찾아 ++ 또는 -- 해주는 방식으로 구현하려고 했다.
그러기 위해서는 찾는 채널의 각 자릿수를 뽑아 고장나지 않은 리모컨 버튼이랑 비교해서 가까운 숫자를 만들어야한다. 그런데 이 방식은 변수가 많고 경우의 수도 많아 코드 작성에 어려움이 있고 이 방법이 확실한 정답을 보장하기에는 어려움이 있다고 생각했다.
다른 방법이 없을까 고민을 했고 수학적인 방식으로는 풀 수 없겠다는 결론에 도달했다.
그래서 백준 알고리즘 분류를 봤더니 완전탐색 문제였다....
많이 부족함을 느끼는 순간이었다.
완전탐색임을 알아도 문제 풀이에 바로 접근하지 못했다.
-
주어진 문제를 선형 구조로 구조화한다.
-
구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
-
구성된 해를 정리한다.
출처: https://hcr3066.tistory.com/26
완전 탐색 문제는 이런식으로 풀이해야한다고 하더라. 구글에서 찾은 블로그에서
1번 부터 적용해나가 보면 문제에서 원하는 채널을 찾아야는데 리모컨 버튼이 고장났다. 그래서 리모컨 버튼에서 고장난 버튼을 0~9까지 리스트에서 제거하는 방식으로 구현했다.
그리고 찾는 채널의 범위가 0 ≤ N ≤ 500,000라서 완전탐색 범위는 0부터 1,000,000이 된다. 이유는 500,000채널로 가는데 100에서 찾아가는 방법이 있고 1,000,000부터 찾아가는 방법이 있기때문이다.
문제를 선형 구조로 구조화했다. 다음은 이제 구조화된 공간에서 답을 찾아야한다. 일단 찾는 채널을 가장 쉽게 가능 방법은 찾는 채널 N에서 100을 뺀만큼 ++ 혹은 --를 해주면 된다. 횟수는 양수이기때문에 abs를 해준다.
그 다음은 버튼을 통해 갈 수 있는 방법인데 버튼을 저장해놓은 리스트에서 해당 버튼을 클릭할 수 있다면 cnt를 증가시키며 숫자를 찾아가는 방식이다.
이 두 경우에서 작은 값을 정답으로 채택하면 된다.
주석으로 추가 설명을 달아놓았다.
import java.io.*;
import java.util.ArrayList;
public class Main {
static int n, s;
static int count = 0;
static ArrayList<Integer> btn;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String num = br.readLine();
int len = num.length();
n = Integer.parseInt(num);
int m = Integer.parseInt(br.readLine());
btn = new ArrayList();
for (int i = 0; i < 10; i++) {
btn.add(i);
}
//고장난 버튼들을 저장
ArrayList broken = new ArrayList();
//만약 m이 0, 즉 고장난 버튼이 0개일 경우 입력을 받지 말아야한다. 이 부문 처리를 안해 처음에 틀렸다.
if (m != 0) {
String[] line = br.readLine().split(" ");
for (int i = 0; i < m; i++) {
broken.add(Integer.parseInt(line[i]));
}
}
//전체 버튼 중 고장난 버튼을 제외
if(m != 0) {
for (Object a : broken) {
Integer t = (Integer) a;
btn.remove(t);
}
}
//시작 위치에서 해당 채널로 ++ 또는 --로만 가는 횟수
int ans = Math.abs(n - 100);
//0부터 1000000까지 모든 채널을 탐색해서 N까지 가는 횟수 구하기
for (int i = 0; i <= 1000000; i++) {
//solution 함수에서 i채널로 이동 가능한지 불가능한지 검사
int cnt = solution(i);
if(cnt>0)
// 둘 중 최소를 선택
//i채널에서 n채널로 가는 횟수+i채널의 길이와 현재 ans값 중 최소값
ans = Math.min(ans, Math.abs(n-i)+cnt);
}
bw.write(ans + "\n");
br.close();
bw.close();
}
private static int solution(int n) {
int cnt = 0;
//n==0일 경우와 아닌 경우 분리
if (n == 0) {
//0이 고장났다면 0을 리턴, 해당 채널로는 이동이 불가능하다는 의미
if (!btn.contains(n))
return 0;
//그렇지 않다면 0채널로 이동한 것이 되니 길이인 1을 리턴
else
return 1;
}
while (n > 0) {
//n의 자릿수 중 하나라도 btn에 포함되어 있지않다면 해당채널로 가는 것은 불가능하기때문에 0을 리턴
if(!btn.contains(n%10))
return 0;
//그 외에는 cnt를 증가시키고 다시 다음 자릿수를 뽑아 반복한다.
cnt++;
n = n/10;
}
return cnt;
}
}
