[백준 BOJ] 1748번 수 이어 쓰기 1 (C++/cpp)

문제 설명

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

1748번: 수 이어 쓰기 1

 

접근 방법 - 수학적 사고력을 요구하는 문제

백준의 1748번 문제는 수학적 사고력을 이용하여 해결해야 하는 문제이다.

해당 문제는, 1부터 입력받은 숫자까지 모두 적어보았을 때 이 숫자의 자릿수를 출력해야 하는 문제이다.

이때 입력값의 최댓값이 너무 크기 때문에 단순 int형으로는 표현할 수 없다는 점을 유의하길 바란다.

C언어나 cpp의 경우엔 long long int형을 사용하면 해결할 수 있는 부분이다.

필자의 경우엔 일일이 숫자를 연결해보아 자릿수를 계산하기보다 각 숫자들의 자릿수를 더하면서 정답을 구해보았다.

이번 코드의 설명은 이해하기에 다소 어려울 수 있기 때문에, 설명을 참고하는 것도 좋지만 코드를 보고 직접 시뮬레이션해보면서 이해해볼 것을 권장하고 싶다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 값(n)을 입력받는다. (단순 int형으로 입력받을 수 없음을 유의해라.)

 

2) 3가지의 변수를 아래처럼 선언한다.

- 최종 결괏값을 저장할 변수 result를 0으로 초기화하여 선언한다.

- 각 숫자의 자릿수에 따라 result에 더할 값을 저장할 변수 cnt를 1로 초기화하여 선언한다.

- 아래의 자릿수 판별 연산에 있어 기준점이 될 변수 num을 1로 초기화하여 선언한다.

(이때 이 변수는, 입력값의 범위를 생각하여 단순 int형으로 선언해서는 안 된다.)

 

3) 제어 변수 i를 1부터 시작하여 n까지 탐색하면서 아래의 연산을 취한다.

숫자는 1부터 시작하기 때문에 cnt의 초기값을 1로 설정한 것이다.

다만, 10, 100 등으로 넘어갈수록 자릿수가 1씩 늘어나기 때문에 아래처럼 실행하도록 한다.

- 만일, 탐색하는 값인 i의 자릿수가 1 증가했다면, 자릿수를 판별하는 데에 기준점이 되는 num에 10을 곱한 뒤 cnt에 1을 더한다.

- 반복문을 거듭할 때마다, result에 현재의 cnt의 값을 더하도록 한다.

 

4) 연산이 끝났다면, 최종적으로 저장된 result의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 1748번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	long long int n;
	cin >> n;

	int result = 0;
	long long int num = 1;
	int cnt = 1;
	for (long long int i = 1; i <= n; i++) {
		while (num * 10 <= i) {
			num *= 10;
			cnt++;
		}
		result += cnt;
	}
	cout << result << endl;
}

 

제출 결과

(2022.05.01 백준 1748번 문제 제출 결과)

왠지 무한 반복문 부분은 if문으로 작성하여도 될 것 같은데;;