首页 > itarticle > 알고리즘 – 숫자의 총 개수 – syunyun

알고리즘 – 숫자의 총 개수 – syunyun

admin 10月 27, 2020 0

문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까? 예를들어 11까지는 1,2,3,4,5,6,7,8,9,1,0,1,1 로 총 12개가 사용되었다.

풀이

가장 단순한 접근방법은, 두자리수 이상의 수들은 자릿수 대로 분해시키면서 갯수를 count하는 방법이다. 하지만 N의 개수가 커지면 시간초과가 걸리게 되므로 다른 방식으로 접근을 해야 한다.
1부터 9까지의 숫자들은 1개씩 숫자를 가지므로 9개가 필요하다. 10부터 99까지는 2개씩 숫자를 가지므로 180개가 필요하다. 위의 규칙을 통해서 수식을 구할 수 있다.

예를들어 입력받은 숫자 N이 256이라면 256까지의 숫자의 총 개수를 구해보는 표를 작성하면 아래와 같다.

 해당 범위의 직전의 마지막 수(l) 자릿수의 개수(d), 해당범위의 총 자연수 갯수(c), 숫자의 총 갯수 (res)
        0                        1                       9                        9
        9                        2                      90                       189
        99                       3                      900                      189 + ((256 - 99)*3)

코드


int () {
    int n,l = 0,d = 1,c = 9 ,res = 0;
    scanf("%d",&n);
    while(c + d < n) {
        res += c * d;
        l += c;
        d++;
        c = c*10;
    }
    res += ((n - l) * d);
    printf("%d",res);
}