[C++] 백준 1748번:수 이어 쓰기1

문제링크

1748번: 수 이어 쓰기 1

문제

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

 

1234567891011121314151617181920212223...

 

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

입력

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

출력

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

 

풀이

두 가지 케이스로 살짝 분리하여 풀이했다.

1.N이 자릿수를 넘어가는 경우 (한 자리수에서 두 자리수로, 두 자리수에서 세 자리수로)

2.N이 자릿수를 넘어가지 않는 경우 (네 자리수인 경우..)

첫 번째의 경우

9보다 크면 한 자리수를 모두 포함하고

99보다 크면 두 자리수를 모두 포함하고

999부도 크면 세 자리수를 모두 포함하고

...

반복된다고 볼 수 있다.

두 번째의 경우

두 자리수라면 9를 빼줘야 하고 세 자리수라면 99를 빼줘야 한다. 그 이유는 10부터는 바로 두 자리수가 되고 100부터 바로 세 자리수가 되기 때문이다.

따라서 N에서 현재 자리수보다 작은 자리수의 최대 값을 (9나 99나 999)를 빼준 뒤 자릿수를 곱해주면 된다.

말로 풀이하니까 조금 어려운데

1 - 9 : 1자리

10 - 99 : 2자리

100 - 999 : 3자리

를 더해준다고 생각하면 된다.

코드

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
 
int n;
ll result;
string num;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
 
    // 자릿수
    int num = 9;    // 자릿수 중에서 가장 큰 수 9 -> 99 -> 999 -> 9999
    int plus = 1;    // 더해줄 자릿수 1 -> 2 -> 3 -> 4 
    int cnt = 9;    // 자리수 반복 횟수 9 -> 90 -> 900 -> 9000
    while (true) {
        // 자릿수가 넘어가면
        if (n > num) {
            result = result + (ll)plus * cnt;
            plus++;
            num = num * 10 + 9;
            cnt = cnt * 10;
        }
        // 아니라면
        else {
            result = result + (n - (ll)(num / 10)) * plus;
            break;
        }
    }
 
    cout << result;
 }