취미로 코딩하기

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

이번에 볼 문제는 백준 24924번 문제인 Card Divisibility이다.
문제는 아래 링크를 확인하자.

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

9의 배수의 잘 알려진 특징 하나를 먼저 상기하고 넘어가자. 바로 x의 모든 자릿수의 합이 또다시 9의 배수가 된다는 것이다.

위 특징의 증명을 조금 더 생각해보면, 임의의 자연수 n에 대하여 n을 9로 나눈 나머지는 n의 모든 자릿수의 합을 9로 나눈 나머지와 같다는 것을 알 수 있다.

n을 9로 나눈 나머지는 n을 이루는 각 자릿수들의 합만으로도 구할 수 있으므로, L부터 R까지를 이어써서 만든 수를 9로 나눈 나머지 또한 L부터 R까지의 수를 이루는 각 자리들의 합을 9로 나눈 나머지와 같다는 것을 알 수 있다.

이들을 다시 L부터 R까지의 각각의 수 단위로 끊어 거꾸로 생각하면, 결국 구하는 값은 L부터 R까지의 각 수의 총합을 9로 나눈 나머지와 같다는 것을 생각해낼 수 있다.

__int128을 이용하여 L부터 R까지의 수의 총합, 즉 "(R-L+1)*(L+R)/2"를 9로 나눈 나머지를 계산하자.

__int128을 사용하지 않고 해결할 수 있는 방법도 있다. 0부터 8까지의 수를 더하면 9의 배수가 된다는 점을 이용하여, 연속한 9개의 수들은 직접 더하지 않아도 된다는 점을 이용하는 것이다.

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

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

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

	ll L, R; cin >> L >> R;
	int128 LL = L, RR = R;
	int ans = (int)(((RR - LL + 1) * (L + R) / 2) % 9);;

	cout << ans;
}