[백준 / C언어] 1748번: 수 이어 쓰기 1

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

1748번: 수 이어 쓰기 1

 

난이도: solved.ac 실버 4

 

 

접근 방식

---

1. 자릿수가 같은 수들끼리 묶는다

2. 각각을 나열해서 자릿수를 세어본다

3. 각각의 자릿수를 모두 합한다

 

세부 설명

---

예시를 들어 설명해 보겠다

 

1부터 54298까지의 수를 나열해 만든 수의 자릿수를 구한다고 해보자

 

나열하는 수의 구간을 쪼개어보자

 

10000 ~ 54298 까지 나열 (모두 다섯 자릿수라는 공통점이 있음)

1000 ~ 9999 까지 나열 (모두 네 자릿수)

100 ~ 999 까지 나열 (모두 세 자릿수)

10 ~ 99 까지 나열 (모두 두 자릿수)

1 ~ 9까지 나열 (모두 한 자릿수)

 

먼저, 10000부터 54298까지의 수를 나열했을 때의 총 자릿수를 구해보자

 

10000부터 54298까지의 수는 54298 - 10000 + 1 = 44299 개이며, 모두 다섯 자릿수이므로

 

44299 * 5 = 221495 가 된다

 

두 번째로 1000부터 9999까지의 수를 나열해서 총 자릿수를 구해보자

 

1000부터 9999까지의 수는 9999 - 1000 + 1 = 9000 개이고, 모두 네 자릿수이므로

 

9000 * 4 = 36000 가 된다

 

세 번째로 100부터 999까지의 수를 나열해서 총 자릿수를 구해보면

 

(999 - 100 + 1) * 3 = 2700 가 된다

 

이 정도면 메커니즘이 이해될 테니 이후는 생략하겠다

 

종합하면 다음과 같다

 

10000 ~ 54298 까지 나열

→ (54298 - 10000 + 1) * 5 = 221495

1000 ~ 9999 까지 나열

→ (9999 - 1000 + 1) * 4 = 36000

100 ~ 999까지 나열

→ (999 - 100 + 1) * 3 = 2700

10 ~ 99 까지 나열
→ (99 - 10 + 1) * 2 = 180
1 ~ 9까지 나열
→ (9 - 1 + 1) * 1 = 9

 

총 221495 + 36000 + 2700 + 180 + 9 = 260384 가 된다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int ppow(int a, int b);	// pow 함수를 int로 쓰면 오류날까봐 직접 만듦

int main() {
	int N;
	long long ans = 0;
	scanf("%d", &N);
	int temp = N, power = 0;	// power: N이 몇 자리 수인지

	while (temp) {	// N이 몇 자리 수인지 파악하는 과정
		power++;
		temp /= 10;
	}

	// 위의 예시에서 10000 ~ 54298까지 나열했을 때 자릿수를 구하는 과정
	int w = ppow(10, power - 1);
	temp = N - w + 1;
	temp = temp * power;
	ans = ans + (long long)temp;
	power--;

	// 나머지를 나열해서 자릿수를 구하는 과정
	while (power) {
		w = ppow(10, power - 1);
		temp = w * 9 * power;
		ans += temp;
		power--;
	}

	printf("%lld", ans);
	return 0;
}

int ppow(int a, int b) {
	int res = 1;
	while (b) {
		res *= a;
		b--;
	}
	return res;
}