백준 1081 합
문제는 간단하다.
두 정수 L과 U가 주어지고, L 이상 U이하인 모든 정수의 각 자리의 합을 구하면 된다.
다만 문제를 푸는 알고리즘을 생각하기까지의 과정은 간단하지 않았다.ㅜㅜ
첫번째로 생각했던 과정은 다음과 같다.
일단 0-9까지의 합이 45이고, 10, 100, 1000처럼 10의 제곱근 단위로 나누어 이를 이용해야 한다는 생각까진 들었다.
다만 이걸 어떻게 이용해야하나? 하는 고민이 많았다.
예시로 1129와 2712의 정수가 주어졌다고 가정해보자.
제일 앞자리 1은 뒤에 있는 숫자의 개수만큼 나오는 개수가 달라질거고, 그건 각 자리가 마찬가지다.
두 정수의 차를 구해서 서로에게 영향이 없는 (eg. 102와 493일때 200-400까지는 영향이 없는 것을 의미) 수를 구해서 그만큼은 정해진 값을 더하고 나머지 바뀌는 부분만 따로 계산해야 할까?
하는 뒤죽박죽한 생각이 계속 들었던 것 같다.
이 한 문제를 고민한다고 오랜 시간을 쓰는 것은 원하지 않았기 때문에 차선책으로 생각한 방법은 우리의 친구 ChatGPT였다..ㅎㅎ
물론 처음부터 문제를 주고 알려줘! 하라는 것이 아니다.
문제를 주고 친절하게 '난 이 문제를 풀고 싶은데, 네가 한 번에 알려주는 것을 원하지 않아. 내가 해결 방법을 찾을 수 있게 상황에 맞는 힌트를 줄 수 있을까?'라고 작성해서 물어봤다.
(물론 큰 도움이 된 것 같지는...ㅎ.ㅎㅎ)
결국 생각한 방법은
0-N까지 각 자리의 수를 구하는 함수를 만들고 두 정수를 각각 구해서 빼자! 였다.
그래서 이리저리 생각하며 고민한 결과
0-10의 n제곱 까지의 각 자리의 합을 구하고 나머지는 따로 구하는 방법이다.
0에서 10의 n제곱까지 구하는 공식은 다음과 같았다.
10의 n제곱까지 각 자리의 합을 구하는 공식
0 ~ 10^1 - 1 = 45 * 10^0
0 ~ 10^2 - 1 = 45 * 10^1 + 45 * 10 = 900
0 ~ 10^3 - 1 = 45 * 10^2 + 900 * 10 = 13500
0 ~ 10^4 - 1 = 45 * 10^3 + 13500 * 10 = 180000
...
0 ~ 10^n - 1 = 45 * 10^(n-1) + (10의 n-1제곱까지의 각 자리의 합) * 10
그래서 일단 주어진 정수가 몇 자리인지 구하고 주어진 자리수까지의 각 자리의 합을 구했다.
그 뒤에 나머지를 구하는 과정을 거쳤다.
다음이 내가 작성한 코드이다.
int pow = (int) Math.log10(n); // n의 자리수 eg)2345일 경우 pow = 3
long base = powers[pow]; // 10^pow
long firstDigit = n / base; // 맨 앞자리수 eg) 2345일 경우 2
long remainder = n % base;
long res = (arr[pow] * firstDigit) // 이전 자릿수들의 누적 합
+ (firstDigit * (remainder + 1)) // 나머지의 앞자리수 미리 더하기
+ (firstDigit * (firstDigit - 1) / 2 * base); // 이전 자리수 첫번째 자리
예시 값을 넣어서 설명을 추가하자면
만약 값이 2345가 들어왔다고 가정하여 코드를 봐보도록 하자.
여기서 pow는 숫자의 자리수이다. 다만 2345의 경우 4자리수이지만 pow는 3이라는 값을 가진다는 점을 유의하자.
원래라면 +1을 하여 4자리라고 하는 게 맞겠지만 우리가 사용해야 할 것은 자리수가 아닌, 자리수를 이용해 구하는 1000이라는 단위다.
1000은 10의 3제곱을 이용해 나오는 수이기 때문에 3에 1을 더하지 않고 10에 제곱하여 1000이라는 수를 쓸 것이다.
그렇게 1000값을 이용하여 주어진 정수의 첫번째 자리값인 firstDigit과 나머지값인 remainer를 구하는 것이다.
마지막으로 res를 살펴보자.
arr[pow] * firstDigit는 0-999까지의 합이다. 실제로는 0-999까지의 합이 앞자리가 0일때, 1일때 총 두번 반복되기 때문에 첫번째 자리수를 곱하여 구해준다.
firstDigit * (remainder + 1)는 나머지를 위한 사전준비다.
345라는 값이 remainder에 남지만 실질적으로는 2001부터 2345까지 앞에 2라는 숫자가 들어있다. 그래서 실제로는 2가 345번 반복되어 나오기 때문에 345라는 값만 보내주기 위해 앞의 2를 미리 더해주는 것이다.
firstDigit * (firstDigit - 1) / 2 * base는 앞의 0-1999까지의 첫번째 자리수를 구해주는 코드다. 0-999까지의 합이 두 번 반복되는 동안 앞자리의 0이 999번, 1이 999번 반복되는 것은 더해주지 않았기 때문에
이 코드를 이용해서 앞자리의 합을 구해주는 것이다.
이런 과정을 이용해서 결론적으로 전체 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* BOJ 1081 합
* @author JOMINJU
*
* L과 U라는 정수가 주어진다. L 이상 U 이하의 모든 정수의 각 자리의 합을 구해라.
*
*
* 0-9까지의 합은 45
* 0-L까지의 각 자리의 합을 구하고 0-U까지의 각 자리의 합을 구해서 빼기
* @구해야 할 것: 0-N까지의 각 자리의 합.
* 10의 n제곱까지 각 자리의 합이 얼마나 되는지 구하고 그 나머지만 따로 구하기
*
* 10의 n제곱까지의 각 자리의 합을 구하는 방법
* 45 * 10 ^ n + [n-1의 각 자리의 합] * 10
*
*/
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringBuilder sb = new StringBuilder();
public static long[] arr = new long[10]; // 누적 합 배열
public static long[] powers = new long[10]; // 10의 제곱 배열
public static void main(String[] args) throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int U = Integer.parseInt(st.nextToken());
precompute(); // arr[]와 powers[] 계산
long sumL = sum(L - 1);
long sumU = sum(U);
sb.append(sumU - sumL);
System.out.println(sb);
}
public static void precompute() {
arr[1] = 45; // 0-9의 합
powers[0] = 1;
// 각 자리수 별 구하는 공식
for (int i = 1; i < 10; i++) {
powers[i] = powers[i - 1] * 10;
arr[i] = 45 * powers[i - 1] + arr[i - 1] * 10;
}
}
public static long sum(long n) {
if (n <= 0) return 0;
int pow = (int) Math.log10(n); // n의 자리수 eg)2345일 경우 pow = 3
long base = powers[pow]; // 10^pow
long firstDigit = n / base; // 맨 앞자리수 eg) 2345일 경우 2
long remainder = n % base; // 나머지 수 eg) 2345일 경우 345
long res = (arr[pow] * firstDigit) // 이전 자릿수들의 누적 합
+ (firstDigit * (remainder + 1)) // 나머지의 앞자리수 미리 더하기
+ (firstDigit * (firstDigit - 1) / 2 * base); // 이전 자리수 첫번째 자리
return res + sum(remainder);
}
}
바보같이 고민도 했고, 사실 조금의 시간이 지난 뒤에 다시 풀어보면 헷갈릴 것 같은 문제다.
조금의 시간이 지난 뒤에 다시 한번 풀어보도록 하자!