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으로 나누어 마지막 자릿수를 제거합니다.
이렇게 자릿수를 더하고 그 결과를 입력받은 값과 비교에서 같으면 반복문을 종료하고 출력한다.
정말 여러모로 많이 배울 수 있는 시간이었다.