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

1. 문제이해

1748번: 수 이어 쓰기 1 (acmicpc.net)

1748번: 수 이어 쓰기 1

 

1부터 N까지의 숫자를 이어서 쓰면 새로운 수를 얻을 수 있다.

이렇게 만들어진 새로운 숫자는 몇 자리 수인지 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

1부터 N까지의 숫자를 이어 썼을 때, 이어쓴 숫자가 몇 자리 수인지를 출력하는 것이 목표이다.

예를 들어, N이 8인 경우에는 12345678 이라는 8자리 수가 나타나며,

N이 12인 경우에는 123456789101112 라는 15자리 숫자가 나타나게 된다.

N의 값에 따라서 몇 자리 숫자가 나오게 되는지 아래 예제를 통해 확인하자.

 

 

1. N이 한 자리 자연수인 경우 ( ex) 8 )

N = 8 이므로, 만들어지는 숫자는 12345678 총 8자리 이다.

일의 자리 숫자는, 한번에 한 자리씩 더해지므로,

N이 한 자리 자연수인 경우, N이 곧 만들어진 숫자의 자릿수가 되게 된다.

 

 

2. N이 두 자리 자연수인 경우 ( ex) 12 )

N = 12 이므로, 만들어지는 숫자는 123456789101112 총 15자리이다.

1부터 9까지는 한자리씩 더해지므로, 9까지 쓰게 되면 9자리 수가 나타나게 된다.

하지만, 10부터는 두 자리씩 더해지기 때문에,

한자리 자연수 9개를 제외한 10, 11, 12는 두 자리 씩 더해주어야 한다.

따라서, 총 자릿수 = (12 - 9) x 2 + 9 = 15 가 된다.

 

즉, 두 자리 자연수의 경우 총 자릿수 = (N - 9) x 2 + 9 가 된다.

(여기서 N- 9의 9를 빼준 이유는, 총 N개의 숫자 중 9개는 일의 자리 숫자이기 때문.

이후 x2를 하여 두 자리씩 더해주고, 마지막에 9를 더해줌으로서 한 자리 숫자들도 세어줌.)

 

 

3. N이 세 자리 자연수인 경우 ( ex) 120 )

N = 120 이므로, 만들어지는 숫자는 1234567891011121314....120 총 252자리이다.

1부터 9까지는 한자리씩 더해지므로, 9까지 쓰게 되면 9자리 수가 나타나게 된다.

그리고 10부터 99까지는 두자리씩 더해지므로, 90 x 2의 자리수가 더해지게 된다.

한자리, 두자리 자연수 99개를 제외한 나머지 세자리 숫자들을 3자리씩 더해주어야 된다.

따라서, 총 자릿수 = (120 - 99) x 3 + 90 x 2 + 9 = 252 가 된다.

즉, 세 자리 자연수의 경우 총 자릿수 = (N - 99) x 3 + 90 x 2 + 9 가 된다.

 

 

위와 같이 규칙들을 적용해나가보면,

N이 4자리 자연수인 경우의 자릿수는 (N - 999) * 4 + 900 * 3 + 90 * 2 + 9

N이 5자리 자연수인 경우의 자릿수는 (N - 9999) * 5 + 9000 * 4 + 900 * 3 + 90 * 2 + 9

N이 6자리 자연수인 경우의 자릿수는 (N - 99999) * 6 + 90000 * 5 + 9000 * 4 + 900 * 3 + 90 * 2 + 9

.

.

.

와 같은 양상을 띄게 된다.

즉, N이 D자리 자연수인 경우의 자릿수는 다음과 같다.

(N - (9를 D-1번 반복)) * D + 나머지 자릿수들의 합

이를 코드에 적용해본 결과는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
	long long N;
	long long tmpN;
	long long result = 0;
	int digit = 0;			// N이 몇 자리 정수인지를 나타냄
	string num = "9";

	cin >> N;
	tmpN = N;

	// N이 몇자리 정수인지 구하기
	while (tmpN > 0) {
		digit++;
		tmpN /= 10;
	}

	if (digit == 1) {	// 일의 자리인 경우, 그대로 출력
		cout << N;
	}
    
	else {
    		// (digit-1)에 해당하는 만큼 9를 이어줌. (99, 999, 9999 ....)
		for (int i = 2; i < digit; i++) {
			num += "9";
		}
		
        	// num을 int로 변환 후, 나머지 자리수에 해당하는 값을 제외하고 연산
		result += (N - stoi(num)) * digit;
        
		// 나머지 자리수 연산
		while (digit > 1) {
			result += (9 * pow(10, digit - 2)) * (digit - 1);
			digit--;
		}
		cout << result;
	}

	return 0;
}

먼저, 위와 같이 변수들을 설정하고 while문은 통해 N이 몇자리 정수인지를 구한다.

이때, while문 안에 N의 복사본인 tmpN을 통해 연산을 해준다.

(N을 넣어 연산을 해주면, while문이 끝났을 때 N값이 바뀌어 있기 때문)

이후 N의 자릿수를 digit 변수에 대입해준다.

 

if문을 통해, 만약 N이 1자리 정수이면 그대로 N을 출력해주고,

아닌 경우에는 else문의 연산을 진행해준다.

먼저 for문을 통해 (digit - 1)에 해당하는 만큼 num에 9를 붙여주고,

string 인 num 값을 int 형으로 바꿔주어 연산 후 result 값에 더해준다.

(N = 120의 경우, (120 - 99) x 3 + 90 x 2 + 9 = 252 에서

(120 - 99 ) x 3의 부분에 해당하는 연산을 해준 것이다.)

 

이후 while문을 통해, 자리수가 1이 되기 전까지

나머지 자리수를 더해나가는 과정을 반복한다.

(N = 120의 경우, (120 - 99) x 3 + 90 x 2 + 9 = 252 에서

90 x 2 + 9의 부분에 해당하는 연산을 해준 것이다.)

 

 

---

원리는 어렵지 않았던 문제였지만, 막상 코드로 구현하려니 조금 까다로운 문제였다.

자릿수가 적다면야 하나하나 쳐서 구현해도 좋겠지만,

자릿수가 큰 경우에는 역시 규칙을 찾아서 하는 게 좋은 방법인 것 같다. 🤔