백준 1107번: 리모컨

문제 설명

• https://www.acmicpc.net/problem/1107
• 100에서 N까지 최소한의 버튼으로 이동하는 문제입니다.
  • 리모컨의 버튼은 +,-,0~9가 존재합니다.
  • 리모컨은 중간에 몇몇 숫자버튼이 고장나 있을 수 있습니다.

접근법

• N이 최대 6자리 숫자로 10^6이 그렇게 크지 않기 때문에 순열(백트래킹)을 사용했습니다.
• minVal의 초기값을 Math.abs(N-100)으로 설정해줘야 합니다.
• N이 x자리 숫자라고해서 만들어진 숫자가 반드시 x자리 숫자여야 하는건 아닙니다.
  • N이 99_999라면 100_000에서 접근하는 게 더 빠를 수 있습니다.
  • N이 1_000이라면 999에서 접근하는 게 더 빠를 수 있습니다.
    • 이때 더 작은수의 경우 꼭 한자리수 차이가 아니라 그 이상의 차이가 날 수도 있습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer> numSet = new ArrayList<Integer>();
	static int minVal = Integer.MAX_VALUE;

	public static void main(String[] args) {
		for (int i = 0; i <= 9; i++) {
			numSet.add(i);
		}
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		for (int i = 0; i < M; i++) {
			numSet.remove(new Integer(sc.nextInt()));
		}
		minVal = Math.abs(N - 100); // 100에서 방향키로 움직이는 경우 // N==100일때, numSet.size()==0일때를 따로 분기할 필요 없이 이거면 OK
		int[] answer = new int[11];
		Arrays.fill(answer, -1);
		Permu(0, new StringBuilder(), new boolean[11], Integer.toString(N).length(), N);
		System.out.println(minVal);
	}

	public static void Permu(int depth, StringBuilder sb, boolean[] v, int size, int N) {
		if (depth == size + 1) { // 99_999는 100_000에서 -1하는게 더 빠르다
			int now = Integer.parseInt(sb.toString());
			minVal = Math.min(sb.length() + Math.abs(now - N), minVal);
			return;
		}

		if (!"".equals(sb.toString())) { // 100은 99에서 +1하는게 더 빠르다 (자릿수의 차이가 한자리 이상 날 수 있다(size-1로 하면 틀림))
			int now = Integer.parseInt(sb.toString());
			minVal = Math.min((depth) + Math.abs(now - N), minVal);
		}

		for (Integer next : numSet) {
			sb.append(next);
			Permu(depth + 1, sb, v, size, N);
			sb.deleteCharAt(sb.length() - 1);

		}
	}

}