[BOJ1748][C++] 수 이어 쓰기 1

문제

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

1234567891011121314151617181920212223...

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

 

입력

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

 

 

출력

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

 

 

예제 입력 1

120

 

예제 출력 1

252

 

 

출처

· 문제를 만든 사람: author5

 

 

알고리즘 분류

· 브루트 포스

· 구현

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <iostream> using namespace std;   int main() {     int N, size;       cin >> N;          if ((N >= 1) && (N <= 9)) {         size = 1 * N;     }     else if ((N >= 10) && (N <= 99)) {         size = 9 * 1 + (N - 9) * 2;     }     else if ((N >= 100) && (N <= 999)) {         size = 9 * 1 + 90 * 2 + (N - 99) * 3;     }     else if ((N >= 1000) && (N <= 9999)) {         size = 9 * 1 + 90 * 2 + 900 * 3 + (N - 999) * 4;     }     else if ((N >= 10000) && (N <= 99999)) {         size = 9 * 1 + 90 * 2 + 900 * 3 + 9000 * 4 + (N - 9999) * 5;     }     else if ((N >= 100000) && (N <= 999999)) {         size = 9 * 1 + 90 * 2 + 900 * 3 + 9000 * 4 + 90000 * 5 + (N - 99999) * 6;     }     else if ((N >= 1000000) && (N <= 9999999)) {         size = 9 * 1 + 90 * 2 + 900 * 3 + 9000 * 4 + 90000 * 5 + 900000 * 6 + (N - 999999) * 7;     }     else if ((N >= 10000000) && (N <= 99999999)) {         size = 9 * 1 + 90 * 2 + 900 * 3 + 9000 * 4 + 90000 * 5 + 900000 * 6 + 9000000 * 7 + (N - 9999999) * 8;     }     else if (N == 100000000) {         size = 9 * 1 + 90 * 2 + 900 * 3 + 9000 * 4 + 90000 * 5 + 900000 * 6 + 9000000 * 7 + 90000000 * 8 + 9;     }          cout << size << endl;          return 0; }

---

이 문제를 string을 이용하여 문제를 풀어보려고 했었다.

아래는 string을 이용하여 이 문제를 풀기 위해 내가 접근했던 방식을 나타낸 코드이다.

// 메모리 초과
 
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int N;
    string value;
    
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        value.insert(value.length(), to_string(i));                                                                     
    }
    cout << value.length() << endl;
    
    return 0;
}

insert()함수를 사용하여 string value의 끝 부분에 숫자들을 계속 삽입해주고, 최종적으로 string value의 길이값을 출력하는 방식으로 문제를 풀려고 하였다.

하지만 메모리 초과로 인하여 문제를 풀 수 없었다.

그래서 복잡한 알고리즘을 이용하지 않고, 간단하고 빠르게 이 문제를 해결할 수 있는 방법을 찾아내었다.

그 방법은 규칙을 발견하는 것이다.

아래는 내가 발견한 규칙이다.

1~9 : 9                                                                                           > 1*N        
10~99 : 9 + 90*2 = 189                                                                            > 9*1 + (N-10+1)*2 = 9 + (N-9)*2
100~999 : 9 + 90*2 + 900*3                                                                        > 9*1 + 90*2 + (N-100+1)*3 = 9 + 90*2 + (N-99)*3
1000~9999 : 9 + 90*2 + 900*3 + 9000*4                                                             > 9*1 + 90*2 + 900*3 + (N-999)*4 
10000~99999 : 9 + 90*2 + 900*3 + 9000*4 + 90000*5                                                 > 9*1 + 90*2 + 900*3 + 9000*4 + (N-9999)*5            
100000~999999 : 9 + 90*2 + 900*3 + 9000*4 + 90000*5 + 900000*6                                    > 9*1 + 90*2 + 900*3 + 9000*4 + 90000*5 + (N-99999)*6
1000000~9999999 : 9 + 90*2 + 900*3 + 9000*4 + 90000*5 + 900000*6 + 9000000 * 7                    > 9*1 + 90*2 + 900*3 + 9000*4 + 90000*5 + 999999*6 + (N-999999)*7
10000000~99999999 : 9 + 90*2 + 900*3 + 9000*4 + 90000*5 + 900000*6 + 9000000 * 7 + 90000000 * 8   > 9*1 + 90*2 + 900*3 + 9000*4 + 90000*5 + 999999*6 + 9999999*7 + (N-9999999)*8   
100000000 : 9 + 90*2 + 900*3 + 9000*4 + 90000*5 + 900000*6 + 9000000 * 7 + 90000000 * 8 + 9       > 9*1 + 90*2 + 900*3 + 9000*4 + 90000*5 + 999999*6 + 9999999*7 + 99999999*8 + 9 

이 규칙을 이용하여 이 문제를 해결할 수 있었다.