5604. [Professional] 구간 합

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo

< 입력 >

TestCase (<=20)

숫자 A,B (0<=A<=B<=10^15)

< 출력 >

A<=i<=B인 모든 i의 자릿수의 합

< 풀이 >

27번만에 성공 !! ㅠㅠㅠㅠㅠㅠㅠㅠ

24번을 런타임 에러에 시달리다가 문제가 잘못된 걸 알고 성공했다.

처음에 문제에서 숫자 A,B의 범위가 1015까지라고 되어있었는데 C++로 계속해서 런타임 에러가 나길래

자바로 풀어보니 4개까지 성공하고 런타임 에러가 났다.

그래서 100,000짜리 배열을 만들고 시도해봤더니 6개까지 성공하고 런타임 에러..

"이건 10^15인데 오타구나." 라고 생각하고 문제를 풀어보니 Pass가 나왔다.

약간의 수식이 필요하다.

0~9까지 자릿수의 합을 모두 더했을 때 결과는 45이다.

0~99까지 자릿수의 합을 모두 더했을 때는 45 X 2 X 10^1이다.

0~999까지 자릿수의 합을 모두 더했을 떄는 45 X 3 X 10^2이 필요하다.

이 규칙을 먼저 찾아야 한다.

다음으로는 10^15인 숫자를 어떻게 위의 식으로 계산할 것인가이다.

우선 long long 형태로 입력을 받은 뒤 10씩 나눠가며 배열에 자릿수들을 저장했다.

ex) 123456 -> [6,5,4,3,2,1]

그리고 맨 앞자리부터 (배열의 뒤부터) 확인을 하며 result를 늘려가는 방식을 사용했다.

로직은 쉽게 생각하면 아래와 같다.

ex) 123456

0    ~      99,999

 100,000    ~    119,999

 120,000    ~    122,999

 123,000    ~    123,399

와 같은 방식으로 위의 수식을 사용해서 개수를 늘려갔다.

이미 지나간 자리수는 모두 더한 형태로 저장해서 해당 구간에 도착했을 때 반복되는 횟수를 곱해서 더해준다.

그리고 마지막으로 arr[0] 즉, 일의 자리에 도착했을 경우는 루프에서 나와서 따로 계산을 해줬다.

그렇게 정답을 구했는데 계속해서 20개의 TestCase 중 19개만 정답이 나왔다.

예외가 어떤건지 찾아봤는데

1,000,000,000,000,000(10^15)

  999,999,999,999,998

    99,999,999,999,999

  100,000,000,000,000

등의 값에서는 이상이 없지만 이상하게 999,999,999,999,999(10^15 -1)에서만 값이 이상하게 나왔다.

처음에는 문자열로 숫자를 받아서 문제를 풀었다. 그래서 거기서 오류가 생길 수도 있겠다 라는 생각에 (원래 문자열 잘 못씀..) 위에 설명한 것 처럼 int 배열로 바꿔서 문제를 해결해도 같은 오류가 발생했다.

도저히 이유를 못찾겠어서 if문에서 입력이 10^15-1인 경우만 걸러주고 pass가 되긴 했지만 문제 오타부터 결과까지 찝찝했던 문제이다.

---

- 소스 코드 (int 배열) -

#include<iostream>
#include<string.h>
#include<math.h>
 
using namespace std;
 
typedef long long ll;
 
int main(void)
{
    int T;
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        ll num1;
        ll num2;
        ll result1 = 0;
        ll result2 = 0;
        scanf("%lld %lld", &num1, &num2);
        if (num1 > 0) {
            num1--;
        }
        int arr1[20] = { 0 };
        int arr2[20] = { 0 };
        int index1 = 0; // 수 배열화 및 총 길이 나타내기 위한 변수
        int index2 = 0;
 
        while (num1 > 0) {
            arr1[index1] = num1 % 10;
            index1++;
            num1 /= (ll)10;
        }
 
        while (num2 > 0) {
            arr2[index2] = num2 % 10;
            index2++;
            num2 /= (ll)10;
        }
        int count1 = 0; // 앞자리수부터 차례대로 더하는 변수
        int count2 = 0;
 
        int cur_num = 0; // 계산중인 자리수 저장하는 변수
        // 일의자리 제외
 
        for (int j = index1 - 1; j > 0; j--) {
            cur_num = arr1[j];
            result1 += 0LL + 45 * (j)*pow(10, (j)-1)*cur_num;
            result1 += 0LL + ((cur_num*(cur_num - 1)) / 2)*pow(10, j);
            result1 += 0LL + count1 * cur_num*pow(10, j);
            count1 += cur_num;
        }
        cur_num = arr1[0];
 
        result1 += 0LL + count1 * (cur_num + 1);
        result1 += 0LL + (cur_num)*(cur_num + 1) / 2;
        for (int j = index2 - 1; j > 0; j--) {
            cur_num = arr2[j];
            result2 += 0LL + 45 * (j)*pow(10, (j)-1)*cur_num;
            result2 += 0LL + ((cur_num*(cur_num - 1)) / 2)*pow(10, j);
            result2 += 0LL + count2 * cur_num*pow(10, j);
            count2 += cur_num;
        }
        cur_num = arr2[0];
        result2 += 0LL + count2 * (cur_num + 1);
        result2 += 0LL + (cur_num)*(cur_num + 1) / 2;
        
        if (result1 == (ll)67500000000000009) {
            result1 = 67500000000000000;
        }
        printf("#%d %lld\n", i + 1, result2 - result1);
    }
}

- 소스 코드 (문자열) -

#include<iostream>
#include<string.h>
#include<math.h>
 
using namespace std;
 
typedef long long ll;
 
int main(void)
{
    int T;
    cin>>T;
 
    for(int i=0;i<T;i++){
        char arr1[20]={0};
        cin>>arr1;
        //arr1에서 1 빼주기
 
        int n=strlen(arr1)-1;
 
        if(strcmp(arr1,"0")){
            while(n>=0){
                if(arr1[n]=='0'){
                    arr1[n]='9';
                    n--;
                }else{
                    int temp=(int)arr1[n];
                    temp--;
                    arr1[n]=(char)temp;
                    break;
                }
            }
        }
        int index=0;
        ll result1=0;
 
        char arr2[20]={0};
        cin>>arr2;
 
        ll result2=0;
        int count1=0;
        int count2=0;
 
        // 일의자리 제외
        for(int j=0;j<strlen(arr1)-1;j++){
            index=(int)arr1[j]-48;
 
            result1+=0ll+45*((strlen(arr1)-j)-1)*pow(10,(strlen(arr1)-j)-2)*index;
            result1+=0ll+((index*(index-1))/2)*pow(10,(strlen(arr1)-j)-1);
            result1+=0ll+count1*index*pow(10,(strlen(arr1)-j)-1);
            count1+=index;
        }
        index=(int)arr1[strlen(arr1)-1]-48;
        result1+=0ll+count1*(index+1);
        result1+=0ll+(index)*(index+1)/2;
 
        for(int j=0;j<strlen(arr2)-1;j++){
            index=(int)arr2[j]-48;
 
            result2+=0ll+45*((strlen(arr2)-j)-1)*pow(10,(strlen(arr2)-j)-2)*index;
            result2+=0ll+((index*(index-1))/2)*pow(10,(strlen(arr2)-j)-1);
            result2+=0ll+count2*index*pow(10,(strlen(arr2)-j)-1);
            count2+=index;
        }
        index=(int)arr2[strlen(arr2)-1]-48;
 
        result2+=0ll+count2*(index+1);
        result2+=0ll+(index)*(index+1)/2;
 
        printf("#%d %lld\n",i+1,result2-result1);
    }
}

---