[알고리즘 연습] 숫자의 총 개수 (by C++)

숫자의 총 개수

• 특정 숫자 n을 받아서 1~n까지 숫자가 총 몇개 쓰였는지 출력한다.
• 예를 들어, 15를 입력할 경우 1부터 15까지 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였으므로 21이 출력된다.

---

풀이 (단순 접근)

#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);    
    int n, i, j, sum = 0;
    scanf("%d", &n);

    for(i=1;i<=n;i++) {
        for(j=i;j > 0;j = j/10) {
            sum++;
        }
    }

    printf("%d",sum);


    return 0;
}

- 가장 간단하게 위와 같은 코드를 작성할 수 있다.

- 단, 해당 코드는 효율이 좋지 못하여 매우 큰 숫자가 N으로 주어질 경우 문제해결이 어려울 수 있다.

---

풀이 (효율적)

#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);    
    int n, sum = 0, chk = 9, digit = 1;
    scanf("%d", &n);

    while (n > chk) {
        sum += chk * digit;
        n = n - chk;
        chk = chk * 10;
        digit++;
    }

    sum += n * digit;

    printf("%d", sum);    


    return 0;
}

- 따라서 수학적인 접근을 따른다.

- 각 자릿수마다 1씩 증가하면서 숫자를 사용함을 이용한다. (일의자리는 1개, 십의 자리는 2개, ...)

- 자릿수를 체크하면서 반복시키고, 해당 자릿수의 최댓값보다 작을 경우 반복문을 탈출시킨다.

- 위의 코드보다 훨씬 효율적으로 작업을 진행함을 알 수 있다.