2231번 : 분해합

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

 

이 문제는 부분합을 구하는 문제인데,

알고리즘을 보니 브루트포스 알고리즘으로 분류되어 있어서 정말 무식하게 풀었다...

 

내가 생각한 건 1부터 주어진 수까지 1씩 값을 증가시키면서 숫자를 한 자리씩 분리해서 더했다

여기서 num/2를 한 이유는 범위를 반 정도라도 줄이기 위해서 사용했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int result = 0;
        int sum = 0;
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        // i 부터 num 까지 반복
        for (int i = num/2; i < num; i++) {
            // 자릿수 더하기
            for (int j = 0; j < String.valueOf(i).length(); j++){
                // i번째 숫자를 한자리씩 분해하여 정수형으로 바꾼 다음 sum에 더함
                sum += Character.getNumericValue(String.valueOf(i).charAt(j));
            }
            sum += i;

            if(sum == num) {
                result = i;
                break;
            }
            // 초기화
            sum = 0;

        }
        System.out.println(result);
    }
}

 

정말 끔찍하게 풀었지만 일단 맞긴했다;;

아마 브루트포스 알고리즘이 아니었으면 바로 틀렸을 것 같다.

 

여기서 더 개선할 수 있는 방법을 생각해 보면

1. 뒷자리 수부터 차례로 내려간다

2. 자릿수 분해를 문자열로 나누는 게 아니고 산술연산으로 나눈다.

 

이 정도가 생각난다.

 

그래서 한번 Copilot 한테 내 코드의 문제점과 가장 좋은 설루션이 뭐가 있냐고 물어봤다.

---

이 문제는 분해합 (Decomposition Sum)에 관한 문제로, 문제의 입력 숫자 N에 대한 생성자 M을 찾는 것입니다.

주어진 해결 방법은 전체 숫자를 순차적으로 검사하므로 시간복잡도가 높다는 단점이 있습니다. 이를 개선할 수 있는 방법을 제안드릴게요.

더 나은 방법
실제로 이 문제를 해결하는 더 좋은 방법은 역시 브루트포스를 사용하는 것이지만, 모든 숫자를 다 검사할 필요는 없습니다. 다음의 방법으로 계산을 줄일 수 있습니다:

1. 최소 탐색 범위 설정:
   - 보통 생성자의 범위는 N - 9\*자릿수 정도로 한정할 수 있습니다. 예를 들어, 입력 숫자가 100이라면, 100 - 9\*3 = 73부터 시작할 수 있습니다. 이는 각 자리 숫자가 9인 최대 경우의 수를 고려한 것입니다.

2. 생성자 계산:
   - 각각의 숫자에 대해서 각 자리의 숫자 합을 구하고 이를 더해 나갑니다. 이를 통해 분해합을 계산합니다.

다음은 개선된 코드 예제입니다:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int result = 0;

        for (int i = Math.max(1, num - 9 * String.valueOf(num).length()); i < num; i++) {
            int sum = i;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }

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

설명
- 범위 설정: `num - 9 * String.valueOf(num). length()`를 이용해 최소 탐색 범위를 설정합니다.

                    예를 들어, `100`인 경우 `100 - 9*3 = 73`부터 시작합니다.
- 생성자 계산: `i`의 각 자릿수를 더하는 방식으로 분해합을 계산합니다.

이렇게 하면 불필요한 계산을 줄여 성능을 개선할 수 있습니다. 이 방법을 사용하면 좀 더 효율적으로 문제를 해결할 수 있을 거예요. Happy coding! 🎉

---

솔직히 범위를 저렇게 까지 줄일 수 있을 줄은 생각도 못했다.

for문에 대한 설명을 조금 더 자세히 물어봤는데

 

1. String.valueOf(num). length() : 

num을 문자열로 변환하여 길이(자릿수)를 구하고,

 

2. num - 9 * String.valueOf(num). length():

탐색의 최소 범위를 설정하기 위해서 num에

1의 자리 숫자 중에 가장 큰 9를 자릿수와 곱한 값을 뺀다.

예를 들어, num이 100이라면, 100 - 9 * 3 = 73이 된다.

 

3. Math.max(1, num - 9 * String.valueOf(num). length()):

음수를 피하기 위해서  1보다 작다면 1을 반환한다.

정말 죽었다 깨어나도 이렇게 생각하진 못했을 것 같다

 

다음으로 while문에서는

while (temp > 0): temp가 0보다 클 때까지 반복합니다.

• sum += temp % 10: temp의 마지막 자릿수를 sum에 더합니다.
• temp /= 10: temp를 10으로 나누어 마지막 자릿수를 제거합니다.

이렇게 자릿수를 더하고 그 결과를 입력받은 값과 비교에서 같으면 반복문을 종료하고 출력한다.

 

정말 여러모로 많이 배울 수 있는 시간이었다.