[백준] 1081(합) c언어 - 미해결

문제

L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L과 U이 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

#include <stdio.h>

int fun(int i) {
  int sum = 0;
  int j = i;
  while(i > 9) {
    j = i % 10;
    i /= 10;
    sum = i+j;
  }
  return sum;
}

int main() {
  int a, b;
  scanf("%d %d", &a, &b);
  unsigned int sum = 0;

  for(int i=a; i<=b; i++) {
    if(i >= 10) {
      sum += fun(i);      
    }
  }
  printf("%d\n", sum);
}

 

• a부터 b까지 for문 반복
• 만약, i가 10보다 크다면 함수를 사용해서 10으로 계속 나누고 그 나머지와 몫을 더한다.

 

문제 

계속 시간 초과가 떴음. 

3자리까지는 잘 되는데, 마지막 입력은 제대로 돌아가지 않았음 

24660 308357171

그래서 합계를 더하는 함수와 변수 sum을 long long 으로 선언하고 다시 실행해보았음.

값은 나오지만 정확한 답은 아님. 

단순하게 하나하나 계산하는 것보다 규칙을 찾아서 알고리즘으로 만드는 게 이 문제의 핵심인듯함.

0~9까지 각 자릿수마다 숫자가 각각 몇개 나오는지 계산? 

 

https://dreamtreeits.tistory.com/210

 

 

위 블로그 보고 참고해서 만든 알고리즘.. (아직 미해결)

#include <stdio.h>

int main() {
  int a, b;  //10 14
  scanf("%d %d", &a, &b);
  long long int sum = 0;

  int a_arr[10] = {0,};
  int b_arr[10] = {0,};

  int point = 1;
  a -= 1; //9
  int tmp = 0;
  
  while(a > 0) {
    tmp = a % 10;
    if(tmp != 9) {
      a_arr[tmp] += point;
    }
    else 
      a_arr[tmp] += point;
    a -= 1;
    // printf("a %d %d\n", tmp, a_arr[tmp]);
  }

  for(int i=1; i<=b; i++) {
    tmp = i % 10;
    if(tmp != 9) 
      b_arr[tmp] += point;
    else
      b_arr[tmp] += point;
    // printf("b %d %d\n", tmp, b_arr[tmp]);
  }

  for(int i=0; i<10; i++) {
    if(i == 0) 
      sum += (b_arr[i] - a_arr[i]);
    printf("a : %d\n", a_arr[i]);
    printf("b : %d\n", b_arr[i]);
    sum += (b_arr[i] - a_arr[i]) * i;
    printf("%d : %llu\n\n", i, sum);
  }
}

 

모르겠다...