디지털 DP - 숫자 1 수

1009 숫자 1의 수량
기준 시간 제한: 1초 공간 제한: 131072KB점수: 5난이도: 1급 알고리즘 문제
1부터 N까지의 모든 양의 숫자를 적은 십진수 N을 지정하여 1의 개수를 계산합니다.
예를 들어 n = 12 에는 1 이 5 개 들어 있습니다.1,10,12에는 3개의 1,11에는 2개의 1,총 5개의 1이 포함된다.
Input

  N(1 <= N <= 10^9)

Output

    1   

Input 예

12

Output 예

5

dp[i]는 1~10^(i-1)내 숫자 1의 개수를 나타낸다

for(int i=1;i<15;++i)
{
      dp[i]=dp[i-1]*10+po;
      po*=10;
}

그리고 모든 숫자에 대해 숫자와 1의 관계를 고려해야 한다.예를 들어 141과 같이 세 번째 1이 되었을 때 사실상 1~41의 1의 수량을 계산해 냈다. 그러면 나는 이 수량을 100~141에서 시작의 1의 수량을 제외하고 42개의 시작의 1을 더하면 이것은 아직 계산하지 않았다고 생각했다.그리고 또 하나는 1~99의 1의 수량이다.

    if(digit>1) ans+=digit*dp[i-1]+po;
    else if(digit==1) ans+=dp[i-1]+tail+1;

여기의ans는 끊임없이 누적되어 각 위의 1의 숫자를 표시해야 한다.
code:

#include 
#include 
#include 
#define LL long long

using namespace std;

LL dp[15];

void init()
{
    memset(dp,0,sizeof(dp));
    LL po=1;
    for(int i=1; i<15; ++i)
    {
        dp[i]=dp[i-1]*10+po;
        po*=10;
    }
}

int main()
{
    LL x;
    init();
    while(scanf("%lld",&x)!=EOF)
    {
        LL po=1,tail=0,ans=0;
        int digit,i=1;
        while(x)
        {
            digit=x%10;
            x/=10;
            if(digit>1) ans+=digit*dp[i-1]+po;
            else if(digit==1) ans+=dp[i-1]+tail+1;
            ++i;
            tail+=digit*po;
            po*=10;
        }
        printf("%lld
",ans);
    }
    return 0;
}