취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13245번 문제인 Sum of digits이다.
문제는 아래 링크를 확인하자.

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

0부터 N까지의 음이 아닌 (십진수) 정수에 등장하는 모든 자릿수의 합을 구하는 문제이다.

k자리수의 각 자리의 합들을 미리 구해둔 다음, 가장 큰 자릿수부터 하나씩 줄여나가는 식의 관계를 찾아 해결할 수 있다.

예를 들어, 0부터 375까지의 정수의 모든 자릿수의 합은 0부터 299까지의 자릿수의 합과 300부터 375까지의 3 76개, 그리고 0부터 75까지의의 모든 자릿수의 합으로 계산할 수 있다. 이와 같은 관계를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

string s;
ll dgtsum[18]; // [k]: k자리 수들의 각자리합
ll numcnt[18]; // [k]: k자리 수의 개수(leading zero 포함)

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	numcnt[0] = 1;
	for (ll i = 1; i < 18; i++) numcnt[i] = numcnt[i - 1] * 10;

	dgtsum[0] = 0, dgtsum[1] = 45;
	for (ll i = 2; i < 18; i++) {
		dgtsum[i] = 10 * dgtsum[i - 1] + 45 * numcnt[i - 1];
	}

	cin >> s;
	while (s.length() < 18) s = "0" + s;

	ll ans = 0;
	for (ll i = 0; i < 18; i++) {
		ll tmp = s[i] - '0';
		while (s[i] > '0') {
			ans += (ll)(s[i] - '0' - 1) * numcnt[17 - i] + dgtsum[17 - i];
			s[i]--;
		}
		ans += tmp * (stoll(s) + 1);
	}

	cout << ans;
}