취미로 코딩하기

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

이번에 볼 문제는 백준 24394번 문제인 123456789점이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어진 식의 뒤의 "+a"부분은 a가 정수이므로 floor function의 밖으로 빼내 생각해도 무방하다. 해당 부분을 빼내고 남은 식을 f라 하자.

노트의 개수가 20,000 이하라는 점으로부터, 2a+2b+c값이 서로 다르면 점수 또한 서로 다를 수밖에 없다는 점을 관찰하자. 이는 1,000,000,000 / 20,000 = 50,000이므로 2a+2b+c의 값이 1 증가하면 점수는 최소 50,000점 올라가는 데에 반해 +a 항으로 올릴 수 있는 점수는 많아야 20,000점이기 때문이다.

따라서, f의 값이 목표하는 점수와 같거나 작게 나오게 하는 가장 큰 2a+2b+c의 값을 찾는 것으로 문제를 해결할 수 있다.

이와 같은 값은 이진탐색 등의 방법으로 찾아낼 수 있다. 2a+2b+c의 값이 증가하면 f의 값도 증가하는 관계에 있기 때문이다.

이 때의 a의 값은 (목표하던 점수) - f로 계산할 수 있는데, 계산으로 나온 2a+2b+c의 값과 a의 값이 서로 모순된다면 -1을, 그렇지 않다면 그 값을 출력해 문제를 해결하자.

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

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

ll N, goal;
ll func(ll k) {
	return 1000000000LL * k / (2 * N);
}

void solve() {
	cin >> N >> goal;
	ll L = 0, R = N * 2;
	while (L < R) {
		ll mid = (L + R) / 2 + 1;
		ll tmp = func(mid);
		if (tmp <= goal) L = mid;
		else R = mid - 1;
	}
	ll aaaa = goal - L * 1000000000LL / (2 * N);

	if (L < aaaa * 2) cout << -1 << '\n';
	else cout << L << ' ' << aaaa << '\n';
}

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

	int T; cin >> T;
	while (T--) {
		solve();
	}
}