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

학교에서 진행하는 수업에서 같이 듣는 팀원이 공유한 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 4이다.

문제 링크

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

문제 분석

해당 문제는 1부터 n까지의 숫자를 이어 붙여 만들어낸 새로운 수의 자리수를 구하는 문제이다.

문제 풀이

새로운 수의 자릿수를 구하려 하다 보면 1 ~ 9는 1, 10 ~ 99는 2, 100 ~ 999는 3... 이렇게 자릿수가 늘어날 때마다 1씩 증가한 수를 더해주는 것을 알 수 있다. 이를 토대로 아래와 같은 순서를 지키며 코드를 구현할 수 있다.

1. 자릿수의 값을 초기에는 0으로 지정한다
2. 숫자가 10 이하일 경우 자릿수의 값에 1을 더한다
3. 숫자가 10 이상이고 100보다 작으면 자릿수의 값에 2를 더한다
4. 숫자가 100 이상이고 1000보다 작으면 자릿수의 3을 더한다.
   ...

1부터 N까지 위의 과정을 반복한다.

전체 코드

위의 작업을 종합해 작성한 전체 코드는 다음과 같다.

#include <iostream>

using namespace std;

int N;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int current_count = 1;
    int current_max = 10;
    int result = 0;

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        if (i >= current_max)
        {
            current_count++;
            current_max *= 10;
        }
        result += current_count;
    }

    cout << result << '\n';

    return 0;
}

 

결과