[Baekjoon] 수 이어 쓰기 1

👀 문제 설명

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

 

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

 

예제 입력 1

120

 

예제 출력 1

252

 

✍🏻풀이

처음에는 DP를 사용해서 풀려고 했으나, 메모리 초과가 났다.

그래서 자릿수를 사용해서 문제를 풀었다.

 

먼저, 입력받은 N의 자릿수를 구하고, (예제 입력 1을 예로 들면)

N의 자릿수는 3이므로, for문을 사용해 2까지 돈다. 한 자릿수와 두 자릿수는 모두 붙인 길이에 포함될 것이므로, 

1 * 9 + 2 * 90 을 answer에 더해준다. (만약 N의 자릿수가 4라면 1 * 9 + 2 * 90 + 3 * 900을 더할 것이다.)

세 자릿수인 경우도 더해야 하는데, 100부터 120까지 21개의 수를 더해야 하므로, 3 * 21을 더해주면 된다.

 

코드

#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    cin >> N;

    int answer = 0;
    string str = to_string(N);
    for (int i = 1; i < str.length(); i++) {
        int num = 9 * pow(10, i - 1);

        answer += i * num;
    }

    int minus = pow(10, str.length() - 1) - 1;
    answer += str.length() * (N - minus);

    cout << answer << "\n";

    return 0;
}