백준(S3) 1748번: 수 이어 쓰기 1 (C언어 C11 C99)

코드를 보기 전에: 이 문제는 브루트포스 알고리즘인것같기도 하고, 동적계획법 알고리즘인것같기도 하다.

이 문제를 단순하게 풀었다면 대부분 시간초과가 나왔을 것이다. 컴퓨터는 1초에 1억번의 계산을 할수 있는데,

이 문제에서는 입력의 값이 1억까지 이기때문이다.

 

공식: 주어진 값 - a + 1을 하면, a (예를들어 100 이면)  세자리 수의 자리수 값을 더한 값이 나온다.

 

Fullcode

#include <stdio.h>
int main()
{
    int num;
    long long result = 0;
    scanf("%d", &num);
    for (int a = 1; a <= num; a *= 10) // 입력된 값에서 1의 자리는 num만큼 있고, 10의 자리는 num-9 (10은 포함하기 때문) 만큼 있어서, A곱하기 10을 했다.
    {
        result += num - a + 1; // 입력된값 - a +1일때 a가 10이면 2자리 숫자를 구하는 것이고, a가 100이면 세자리 숫자의 자리수를 더하는 것이다.
    }
    printf("%lld", result);
}