https://www.acmicpc.net/problem/14629
곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫자 조각을 이어 붙이면 더 큰 숫자를 만들 수 있고, 정말 다양한 조합이 존재한다는 점이 마음에 무척 들었다. 오늘도 준하는 숫자 조각으로 만들 수 있는 가장 큰 숫자인 9876543210을 보면서 흥분을 감추지 못하고 있었다. 그러나 그런 준하를 보다 못 한 강민이는 준하에게 딴지를 걸기 시작했다.
“그거 가지고는 333도 못 만들지? 깔깔깔”
강민이의 도발에 화가 난 준하는 숫자 조각을 빠르게 조합한 후, 강민이에게 대답했다.
“333은 못 만들어도 329를 만들면 별로 차이 안 나!”
그 말을 들은 강민이는 어이가 없었지만 준하를 놀려먹기로 하고 다음과 같이 말했다.
“그래? 그럼 44223344는?”
순간 준하는 머리가 멍해지며 아무런 생각이 들지 않았다. 이대로 가면 준하는 미래에 수포자가 될 것이다. 준하가 수학을 포기하지 않도록 대신 계산해주는 프로그램을 만들어주자.
첫째 줄에 강민이가 질문하는 숫자 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)
첫째 줄에 0부터 9까지의 숫자를 한 번만 사용하여 만든 숫자 중에 N과 가장 차이가 적은 숫자를 출력한다. 답이 여러 개일 경우, 더 작은 숫자를 출력한다.
이 문제는 평범한 백트래킹 문제이지만, 예외 처리 부분이 까다로웠다. 또, 입력 값이 워낙 크기 때문에, 나는 String
으로 처리하였다.
입력 숫자값을 String
으로 받아
문자열의 길이를 세서 10이하
이거나,
숫자가 9876543210
(숫자카드로 만들 수 있는 경우중 가장 큰 수)보다 큰
경우는, 숫자카드를 뽑아 만들 수 있으므로, 백트래킹
을 진행하여 원하는 작업을 진행한다. 그외의 답은 모두 9876543210
이 답이다.
입력 숫자값의 길이가 digit
이라고 하자. 백트래킹은 3가지
경우를 모두 고려해야한다.
digit
인 숫자digit-1
인 숫자digit-1
인 경우 입력 숫자의 자릿수가 1
이면 0
의 자릿수는 없기때문에, digit이 1이 아닐때
의 조건이 들어가야한다.digit+1
인 숫자digit+1
인 경우 입력 숫자의 자릿수가 10
이면 11
의 자릿수는 만들 수 없기 때문에, digit이 10이 아닐때
의 조건이 들어가야 한다.해당 풀이는 스터디의 @이건 님의 도움을 받았다.
전체 코드
package Baekjoon.java.silver;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class boj14629 {
static String Num,answer;
static Long minResult,targetNum;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
minResult = 9876543210L;
Num = br.readLine();
targetNum = Long.parseLong(Num);
if(targetNum>=minResult){
System.out.println("9876543210");
}else if(Num.length()<=10){
boolean[] numbers = new boolean[10];
int digit = Num.length();
dfs(numbers,0,"",digit);
if(digit!=1){
dfs(numbers,0,"",digit-1);
}
if(digit!=10){
dfs(numbers,0,"",digit+1);
}
System.out.println(Long.parseLong(answer));
}
}
private static void dfs(boolean[] numbers,int idx,String myNum,int Max){
if(idx==Max){
Long calNum = Long.parseLong(myNum);
Long result = Math.abs(calNum-targetNum);
if(minResult>result){
minResult = result;
answer = myNum;
}
return;
}
for (int i = 0; i <10; i++) {
if(!numbers[i]){
numbers[i] = true;
dfs(numbers,idx+1,myNum+Integer.toString(i),Max);
numbers[i] = false;
}
}
}
}