[자바] 백준 1490 - 자리수로 나누기 (java)

목차

문제 : boj1490

 

 

필요 알고리즘

• 브루트포스, 수학
  
  • 오히려 무지성으로 풀면 정답인 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  최악의 경우는 123456789 또는 987123456 처럼 1~9 모두로 이루어진 값이 입력으로 들어오는 경우이다. 이 때 lcm(1,2,3,...9)는 2520이다. 따라서 최악의 경우라도 9876543210000 이내로는 2520의 배수가 존재한다. 그러므로 생각보다 정답의 크기는 커지지 않고, long 범위 이내에서 처리 가능하다.

 

  즉, N부터 시작해 뒤에 0~9를 하나씩 붙여보면서 N의 모든 자리수로 나누어떨어지는지 일일이 확인해도 O(10^4) 이내 정도로 처리 가능하다.

 

  사실 처음에 보고 아.. 또 파이썬 각인가;; 싶었는데 일단 자바로 대충 1자리씩 더하는 위 로직으로 풀어서 오버플로우 나는지 시간초과 나는지 확인해보려고 했는데 정답이 떠버렸다 ㅋㅋ 증명도 못해놓고 풀었다고 풀이쓰긴 뭐해서 '특정 범위 이내로 정답이 나옴'을 어떻게 증명해야할지 몰랐는데 윤갓님이 알려주셨다. 감사합니다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    long n;

    private void solution() throws Exception {
        n = Long.parseLong(br.readLine());

        Queue<Long> q = new ArrayDeque<>();
        q.add(n);
        while (!q.isEmpty()) {
            long cur = q.poll();
            if (isPossible(cur)) {
                System.out.println(cur);
                return;
            }

            for (int i = 0; i <= 9; i++) q.add(cur*10+i);
        }
    }

    private boolean isPossible(long cur) {
        long base = n;
        while (base != 0) {
            if (base%10 != 0 && cur%(base%10) != 0) return false;
            base/=10;
        }
        return true;
    }
}