BOJ) 분해합

분해합

2231번: 분해합

풀이

 

어떤 자연수 M과 N이 있을 때, M과 M의 각 자릿수 합이 N이되는 수의 최소값을 구하는 문제다.

범위를 어떻게 줄일지 생각이 나지 않아서, 일단은 DFS로 모든 경우의 수를 만들어서 검증했다.

자릿수 만큼 숫자를 만들고, 문제의 조건에 맞다면 최소값을 최신화해줬다.

 

코드 1

메모리와 시간이 너무 보기 싫었다.

범위를 어떻게하면 줄일 수 있을지 생각하다가, 주어진 숫자의 각 자릿수가 9로만 이루어진 경우가 해당 자릿수에서 나올 수 있는 최대값이 되기 때문에 N에서 이 수를 뺀 범위부터 N-1까지 탐색하면 되는 것을 알아냈다.

 

반복문을 통해 N-자릿수*9(각 자릿수의 합 = 자릿수*9) ~ N-1 까지 M을 탐색했다.가장 작은 수부터 돌다가 조건에 부합하면 반복문을 종료하면서 답을 구했다.반복문을 다 탐색하고도 답이 없다면, 초기화했던 값 0을 출력하도록 했다.

 

코드 2

 

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    final static int DIGIT_UP = 10;
    static int answer, n, len;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        n = Integer.parseInt(inputStr);
        len = inputStr.length();
        br.close();

        solution();
    }

    private static void solution() {
        answer = Integer.MAX_VALUE;
        dfs(0, 0, 0, new LinkedList<>());
        if(answer == Integer.MAX_VALUE) { answer =0; }
        System.out.println(answer);
    }

    private static void dfs(int cnt, int sum, int partSum, LinkedList<Integer> list) {
        if(sum+partSum == n) {
            int total =0;
            for(int num : list) { total = total*DIGIT_UP + num; }
            answer = Math.min(answer, total);
            return;
        }
        if(cnt >len) { return; }

        for(int i=0; i<=9; i++) {
            list.offer(i);
            dfs(cnt+1, sum*DIGIT_UP+i, partSum+i, list);
            list.pollLast();
        }
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    final static int MAX_NUM = 9, DIGIT_SCALE = 10;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int n = Integer.parseInt(inputStr);
        int len = inputStr.length();
        br.close();
        solution(n,len);
    }

    private static void solution(int n, int len) {
        int answer = 0;
        for(int i=n-len*MAX_NUM; i<n; i++) {
            if(getSum(i) == n) {
                answer = i;
                break;
            }
        }
        System.out.println(answer);
    }

    private static int getSum(int n) {
        int tmp =n;
        while(tmp !=0) {
            n += tmp%DIGIT_SCALE;
            tmp /=DIGIT_SCALE;
        }
        return n;
    }
}