[BOJ] 14629 숫자 조각

문제

https://www.acmicpc.net/problem/14629

14629번: 숫자 조각

 

 

접근

• 기본적인 백트레킹(DFS) 문제
• N이 1,000,000,000,000 까지로 매우 크다. 그런데 생각해보면 0부터 9까지 만들 수 있는 것은 9자리로 한정되고 그마져도 9876543210 을 초과하는 순간 답은 9876543210으로 고정된다.
• 그 이외에는 0부터 9까지를 사용하도록 DFS를 만들면서 만들어진 수가 $N$과 얼마나 차이가 나는지를 확인하고 갱신해주면 해결된다.

 

 

정답 코드

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

public class Main {

    static boolean[] visited;
    static long gap = Long.MAX_VALUE;
    static long ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();

        if (Long.parseLong(line) >= 9876543210L){
            System.out.println(9876543210L);
            return;
        }

        visited = new boolean[10];
        ans = -1;

        solve(line, 0, "");

        System.out.println(ans);
    }

    public static void solve(String line, int length, String current){
        if (line.length() == length){
            long N = Long.parseLong(line);
            long result = Long.parseLong(current);

            if (Math.abs(N - result) < gap){
                ans = result;
                gap = Math.abs(N - result);
            }

            return;
        }

        for (int i = 0; i < 10; i++){
            if (!visited[i]){
                visited[i] = true;
                current += String.valueOf(i);

                solve(line, length + 1, current);

                current = current.substring(0, current.length() - 1);
                visited[i] = false;
            }
        }
    }
}