[백준/JAVA] 2231번 : 분해합

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

 

📌 문제 요약 

 

• 자연수 N의 분해합은 N과 N의 각 자릿수의 합이다.
• 자연수 M이 N의 분해합이 될 때, M을 N의 생성자라고 한다.
• N의 가장 작은 생성자를 찾아야 한다.
• 생성자가 없는 경우 0을 출력한다.

 

---

[ 오답 노트 ]

❌ 기존 오답 코드

// https://www.acmicpc.net/problem/2231
package Brute_Force.분해합;

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine(); // "216"
        // 198 = 198 + 1 + 9 + 8 = 216
        int answer = 0;

        // 216 -> 198
        // 216보다 작은 세자리수 중에서 = 100~216까지 수 중 198 찾기
        int sum = 0; // 분해합
        for(int i = (N.length() - 1) * 10; i <= Integer.parseInt(N); i++) {
            // 분해합 = 전체 수 + (각 자릿수의 합)

            // 각 자릿수합 구하기
            int iSum = 0;
            for(int j = 0; j < String.valueOf(i).length(); j++) {
                iSum += String.valueOf(i).charAt(j);
            }

            // 분해합
            sum = i + iSum;

            if(sum == Integer.parseInt(N)) {
               answer = i;
            }
        }

        System.out.println(answer);

    }
}

📌 기존 코드의 문제점

 

1. 탐색 범위 오류 문제

for (int i = (N.length() - 1) * 10; i <= Integer.parseInt(N); i++) {

• 생성자의 탐색 범위를 제한하려는 의도지만, 생성자는 항상 1부터 N-1사이에 있을 가능성이 있으므로 1부터 탐색해야 한다
• 예를 들어, N = 216일 때 범위를 20부터 시작하면 중요한 생성자를 놓칠 수 있다

 

2. 자릿수 합 계산 오류

for (int j = 0; j < String.valueOf(i).length(); j++) {
    iSum += String.valueOf(i).charAt(j);
}

 

• String.valueOf(i).charAt(j)는 char 값을 반환하며, 이 값을 숫자로 변환하지 않으면 ASCII 값이 더해집니다.
• 예를 들어, i=198i = 198i=198일 때 '1'의 ASCII 값은 49이며, 이를 더하면 잘못된 분해합이 계산됩니다.

 

 

3. 가장 작은 생성자 찾기 실패

if (sum == Integer.parseInt(N)) {
    answer = i;
}

 

• 조건을 만족해도 반복문을 계속 실행하기 때문에 마지막 생성자가 출력됩니다.
• 문제는 가장 작은 생성자를 출력하는 것이므로, 조건을 만족하는 순간 반복문을 종료해야 합니다.

 

 

---

[ 정답 코드 & 올바른 풀이 ]

📌 올바른 풀이

 

1. 탐색 범위 오류 문제 해결

 생성자는 항상 1부터 N-1사이에 있을 가능성이 있으므로 1부터 탐색 범위 수정

for (int i = 1; i <= Integer.parseInt(N); i++) { // 1부터 N까지 탐색

 

 

 

2. 자릿수 합 계산 오류 문제 해결

 문자열 변환 없이 temp % 10과 temp /= 10을 사용해 계산

for (int i = 1; i <= Integer.parseInt(N); i++) { // 1부터 N까지 탐색
            int sum = i;
            int temp = i;

            // 자릿수 합 계산
            while (temp != 0) {
                sum += temp % 10; // 마지막 자리수를 더함
                temp /= 10;       // 마지막 자리수를 제거
            }

 

 

 

3. 가장 작은 생성자 찾기 실패 문제 해결

조건을 만족하면 break로 반복문을 종료

if (sum == Integer.parseInt(N)) { // 분해합이 N과 같다면
                answer = i;
                break; // 가장 작은 생성자를 찾았으므로 종료
}

 

---

📌 정답 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine(); // "216"
        // 198 = 198 + 1 + 9 + 8 = 216
        int answer = 0;

        for(int i = 1; i < Integer.parseInt(N)-1; i++) {
            int sum = i; // 분해합
            int temp = i;

            // 각 자릿수 합 계산
            while(temp != 0) {
                // 216 % 10 = 6 ---> sum += 6
                // 216 / 10 = 21
                // 21 % 10 = 1 ---> sum += 1
                // 21 / 10 = 2 
                // 2 % 10 = 2 ---> sum += 2
                // 2 / 10 = 0
                sum += temp % 10; // 마지막 자릿수를 더함 (각 자릿수 더함)
                temp /= 10;  // 마지막 자릿수 제거된 수 temp
            }

            // 분해합이 N과 같다면 결과 반환
            if(sum == Integer.parseInt(N)) {
                answer = i;
                break;
            }
        }

        System.out.println(answer);

    }
}