취미로 코딩하기

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

이번에 볼 문제는 백준 1215번 문제인 잘못 작성한 요세푸스 코드이다.
문제는 아래 링크를 확인하자.

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

N과 K가 주어질 때, K%1 + K%2 + ... + K%N 를 계산하는 문제이다.

이 문제에서 필요한 관찰은 1000%1000, 1000%999, 1000%998, ... , 1000%1을 순서대로 출력해보는 것으로 충분히 할 수 있을 것이다. 바로 K를 나눴을 때 몫이 같은 수들끼리 등차수열을 이루고 있다는 점이다.

brute force를 통해 나머지를 구해 더할 수 있을 정도의 적당한 범위 안으로 들어오면 브루트포스로 답을 구하자.

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

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

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

	ll N, K; cin >> N >> K;
	ll idx = 2;
	ll old = K;
	ll ans = 0;
	if (N > K) ans += (N - K) * K;

	while (K / idx > 100000) {
		ll current = K / idx;
		if (current < N && N <= old) {
			ll cnt = N - current;
			ans += cnt * (K % N + K % (current + 1)) / 2;
		}
		else if (N > old) {
			ll cnt = old - current;
			ans += cnt * (K % old + K % (current + 1)) / 2;
		}

		old = current;
		idx++;
	}

	if (old > N) old = N;
	while (old) {
		ans += K % old;
		old--;
	}

	cout << ans;
}