취미로 코딩하기

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

이번에 볼 문제는 백준 3007번 문제인 숫자 원이다.
문제는 아래 링크를 확인하자.

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

N=3인 경우는 문제를 간단히 해결할 수 있으므로 N이 3보다 큰 경우에 대해 생각해보자.

주어진 원의 i번째 수와 i+1번째 수를 각각 $b_i$와 $b_{i+1}$이라 하자. 이 때, $b_i=a_{i-1}+a_i+a_{i+1}$이고 $b_{i+1}=a_i+a_{i+1}+a_{i+2}$이므로 $b_{i+1}-b_i=a_{i+2}-a_{i-1}$가 성립한다.

위의 관찰을 이용하면 모든 i에 대하여 $a_i$와 $a_{i+3}$의 차들을 각각 구할 수 있다.

N이 3의 배수가 아닌 경우를 생각해보자. 이 경우, 모든 $a_i$를 $a_0=x$를 기준으로 $x+k_i$의 형태로 표현할 수 있다. $b_i$의 총합을 3으로 나눈 값이 $a_i$의 총합과 같다는 점을 이용하면, 식을 세워 $x$의 값을 구해내 문제를 해결할 수 있다.

N이 3의 배수인 경우를 생각해보자. 이 경우, 모든 $a_i$를 $a_0=x,a_1=y,a_2=z$를 기준으로 $x+k_i$ 또는 $y+k_i$ 또는 $z+k_i$의 형태로 표현할 수 있다. $b_i$의 총합을 3으로 나눈 값이 $a_i$의 총합과 같다는 점을 이용하면, 식을 세워 $x+y+z$의 값을 구해내 $x,y,z$의 값을 적절히 정하여 문제를 해결할 수 있다. $x,y,z$의 값을 결정할 때 모든 $a_i$의 값이 1 이상 1000000000 미만이어야 한다는 조건을 만족시켜야 함에 유의하자.

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

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

int N;
ll S[10000];
ll ans[10000];

ll fcnt = 0, total = 0, difftotal = 0,  val;
void func1(int cur, ll diff) {
	difftotal += diff;

	int nxt = cur + 1;
	if (nxt == N) nxt = 0;
	ll nxtdiff = diff + S[nxt] - S[cur];
	nxt += 2;
	if (nxt >= N) nxt -= N;
	if (nxt) func1(nxt, nxtdiff);
	else val = (total - difftotal) / fcnt;

	ans[cur] = val + diff;
}

ll diffs[10000];

void func2(int cur, int s0, ll diff) {
	diffs[cur] = diff;
	difftotal += diff;
	int nxt = cur + 1;
	if (nxt == N) nxt = 0;
	ll nxtdiff = diff + S[nxt] - S[cur];
	nxt += 2;
	if (nxt >= N) nxt -= N;
	if (nxt != s0) func2(nxt, s0, nxtdiff);
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
		total += S[i];
	}

	total /= 3;

	if (N == 3) {
		cout << 1 << '\n' << 1 << '\n' << S[0] - 2;
	}
	else {
		if (N % 3) {
			fcnt = N;
			func1(0, 0);
		}
		else {
			fcnt = N / 3;
			func2(0, 0, 0);
			func2(1, 1, 0);
			func2(2, 2, 0);

			val = (total - difftotal) / fcnt;

			ll mnx = 0, mxx = 0, mny = 0, mxy = 0, mnz = 0;
			for (int i = 0; i < N; i += 3) mnx = min(mnx, diffs[i]), mxx = max(mxx, diffs[i]);
			for (int i = 1; i < N; i += 3) mny = min(mny, diffs[i]), mxy = max(mxy, diffs[i]);
			for (int i = 2; i < N; i += 3) mnz = min(mnz, diffs[i]);
			ll x = -mnx + 1, xR = 999999999LL - mxx;
			ll y = -mny + 1, yR = 999999999LL - mxy;
			ll z = -mnz + 1;
			val -= x + y + z;
			ll tmp = min(xR - x, val);
			x += tmp, val -= tmp;
			tmp = min(yR - y, val);
			y += tmp, val -= tmp;
			z += val;

			for (int i = 0; i < N; i += 3) ans[i] = x + diffs[i];
			for (int i = 1; i < N; i += 3) ans[i] = y + diffs[i];
			for (int i = 2; i < N; i += 3) ans[i] = z + diffs[i];
		}

		for (int i = 1; i < N; i++) cout << ans[i] << '\n';
		cout << ans[0];
	}
}