[백준 12943] 턴 게임 [Java]

문제

http://boj.ma/12934

요약

• i번째 턴을 승리하면 i점을 얻을 때 정확히 x, y점을 만들 수 있는지 확인 후 x를 만들기 위한 최소 승리 횟수를 구하자.
• 불가능한 경우에는 -1을 출력하자.
• 0 ≤ x, y ≤ $10^{12}$

---

풀이 과정

아이디어

x, y가 유효하기 위한, $x + y = \frac{n(n+1)}{2}$를 만족하는 $n$을 찾아야 합니다.

final long N = (long) Math.sqrt(2 * (x + y));

if (N * (N + 1) / 2 != x + y) {
	return -1;
}

x를 만들기 위한 최소 승리 횟수를 구하기 위해서는, n ~ 1을 순차 탐색하며 x를 만들기 위한 수를 차례대로 선택하면 됩니다.

x보다 큰 수가 만들어지면 안되는 점에 유의해야 합니다.

long sum = 0L, cnt = 0L;
for (long i = N; i >= 1; --i) {
	if (sum + i <= X) {
		sum += i;
		++cnt;
		if (sum == X) break;
	}
}

최적화

sum + i가 X보다 크다면, i보다 작은 X - sum을 선택하면 됩니다.

if (sum == X) return cnt;
if (sum + i <= X) {
	sum += i;
	++cnt;
} else {
	return cnt + 1;
}

성능 분석

• 시간 복잡도: O(N)
• 제출결과: Accepted / 108ms(≤ 2s) / 14152KB

---

참고

문제

http://boj.ma/12934

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/12934.java