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

https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

문제 요약

1부터 100,000,000 사이의 정수 N을 하나 입력 받는다.

1부터 N까지 수를 이어 써서 만든 새로운 숫자의 자릿수를 출력하면 된다.

예를 들어, 15를 입력한 경우 새로운 숫자는 123456789101112131415이 되고, 자릿수는 21이 된다.

 

풀이

시행착오를 많이 겪었다. 여러가지 풀이를 떠올렸는데, 다양한 이유로 자꾸 틀렸다.

 

1. queue 이용 -> 메모리 초과

가장 처음엔 단순하게 1부터 N까지의 숫자를 queue에 담아 size를 출력하는 풀이를 생각했다.

두자리 수 이상의 수를 q에 나누어 담는 방법은 숫자를 10으로 계속 나누어 가며 나머지를 찾으면 된다. 

메모리 초과로 틀린 풀이긴 하지만 나는 이런 식으로 했다.

//1748. 수 이어 쓰기 1
//queue 이용 -> 메모리 초과
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 100000008;

int main() {
    int N; scanf("%d", &N);
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        int j = i;
        while (j) {
            q.push(j % 10);
            j /= 10;
        }
    }
    printf("%d", q.size());
}

 

2. 변수 선언하여 자릿수만큼 ++해주기 -> 시간 초과

큐를 안 쓰는 방법으로 int형 변수 count를 선언하여 자릿수를 세도록 다음과 같이 코드를 수정했는데,

이번엔 시간 초과가 떴다.

//1748. 수 이어 쓰기 1
//변수 선언하여 자릿수만큼 ++해주기 -> 시간 초과
#include <iostream>
using namespace std;

int main() {
    int N; scanf("%d", &N);
    int count = 0;
    for (int i = 1; i <= N; i++) {
        int j = i;
        while (j) {
            count++;
            j /= 10;
        }
    }
    printf("%d", count);
}

 

3. 점화식 찾기

위 풀이처럼 입력한 숫자만큼 for문을 돌면서 자릿수를 세면 안되는 것 같다.

숫자를 입력하면 그에 해당하는 출력값을 바로 뱉어내는 계산식이 필요하겠다는 생각이 들어, 수학적으로 접근했다.

 

  (a) 입력 받은 수의 자릿수(digit)를 계산한다.

  (b) (digit - 1)자리 까지의 자릿수는 정해진 값이므로 계산하여 ans에 더한다.

   1부터 9까지의 수는 1자리 수가 총 9개 -> 9 * 10^0 * 1

   10부터 99까지의 수는 2자리 수가 총 90개 -> 9 * 10^1 * 2

   100부터 999까지의 수는 3자리 수가 총 900개 -> 9 * 10^2 * 3

  (c) N(입력 받은 수)까지 나머지 수들을 ans에 더한다.

 

예를 들어 입력 값이 120인 경우,

  (a) digiit = 3이 된다.

  (b) 120 = (1~9) + (10~99) + (100~120) 이렇게 나눌 수 있는데, (1~9) + (10~99) 까지의 합이 b 과정이다.

  (c) 나머지 수 100부터 120까지의 합을 구하여 ans에 더한다. 

 

이 방식으로 풀었을 때 test case도 다 잘 돌아갔는데 자꾸 틀렸다고 나왔다.

식에는 틀린 부분이 없는 것 같은데 왜 자꾸 틀리지 해서 ans를 int형이 아닌 long형으로 바꿔주니 맞았다.

//1748. 수 이어 쓰기 1
//3. 점화식 찾기
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N; scanf("%d", &N);
    int digit = 0, tmp = N;
    long ans = 0;
    
    // (a)
    while (tmp) {			
        digit++;	
        tmp /= 10;
    }
    
    // (b)
    for (int i = 0; i < digit - 1; i++) {			
        ans += 9 * pow(10, i) * (i + 1);
    }
    
    // (c)
    ans += (N - (pow(10, digit - 1) - 1)) * digit;		
    
    printf("%ld\n", ans);
}

 

4. 효율적인 코드

다음과 같은 코드가 가장 효율적인 것 같다.

for문을 한 번 돌 때마다 1의 자리 수, 10의 자리 수, 100의 자리 수,,, 와 같이 세서 count에 더해준다.

//1748. 수 이어 쓰기 1
#include <iostream>
using namespace std;

int main() {
    int N; scanf("%d", &N);
    int count = 0;
    for (int i = 1; i <= N; i *= 10) count += N - i + 1;
    printf("%d", count);
}