백준 2231번 문제풀이 - 분해합

백준 2231번 문제

 

 

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

2231번: 분해합

 

자연수 N의 분해합은 N + 각 자릿수의 합이다. N을 주어졌을 때 N을 만드는 가장 작은 생성자를 출력하도록 하는 문제이다. 이 문제는 브루트 포스 알고리즘을 이용하여 푸는 문제이다.

 

 

 

 

 

코딩

 

1. 내 풀이

public class DecompositionSum {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int check = 0; //생성자체크용
        
        for (int i = 1; i < N; i++) {
            check++; // i에 맞추어 증가 = 생성자
            if (i + i / 100000 // i + 각 자릿수 더하기 = 분해합
                    + i / 10000 % 10
                    + i / 1000 % 10
                    + i / 100 % 10
                    + i / 10 % 10
                    + i % 10 == N) {
                break;
            }
        }
        if (check == N -1) {
            System.out.println(0); // 생성자가 없으면 0출력
        } else {
            System.out.println(check);
        }
    }
}

 

2. 다른 사람 풀이를 참고하여 수정한 코드

 

public class DecompositionSum {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int N_len = s.length(); // 입력받은 N의 길이

        int N = Integer.parseInt(s);
        int result = 0;
        // N - N_length부터 검색
        for (int i = N - N_len * 9; i < N; i++) {
            
            int number = i;
            int sum = 0;
            // 각 자리 수 더하기
            while (number != 0) {
                sum += number % 10;
                number /= 10;
            }

            if (sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

 

수정된 점이 많다.

첫 번째로 각 자리 수를 구하는 방법은 첫 번째 풀이 코드의 if문을 while문으로 간략하게 만들어줄 수 있다.

자릿수가 작을 때 계산의 수가 줄어들게 된다.

두 번째는 알고리즘 개선인데

N = M(생성자) + M1 + M2 + M3 + ··· 자릿수만큼 더하게 된다.

이 때 M은 각 자릿수의 최댓값인 9 × M의 길이를 N에서 뺀 값이 최솟값이 된다.

그래서 for의 시작을 N - 9 × N_length로 하게 된다.

 

 

 

 

 

 

결과

 

1.

 

2.

 

알고리즘을 개선하면서 메모리는 줄고 속도가 빨라진 것을 확인할 수 있다.

 

 

 

 

 

느낀 점

 

알고리즘을 개선할 방법을 생각해보는게 중요하다는 것을 다시 한번 느낄 수 있었고 수학적인 사고가 필요하다는 것을 느꼈다.