ps:problems:boj:12934
턴 게임
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 12934 |
문제명 | 턴 게임 |
레벨 | 골드 5 |
분류 |
그리디 |
시간복잡도 | O(1) |
사용한 언어 | Python |
제출기록 | 32976KB / 72ms |
최고기록 | 56ms |
해결날짜 | 2022/01/31 |
풀이
- 그리디 문제.
- i번째 턴에서 게임이 끝났을 경우, 양쪽이 가져간 점수의 합은 1+2+…+i = i(i+1)/2 이다. i(i+1)/2 = x+y 가 되는 i를 계산해서 총 몇턴이 걸렸는지를 먼저 찾는다. 이러한 i가 없으면 불가능하다고 출력하면 된다.
- i턴동안 x점을 확보할때 가장 승리 횟수를 적게 하는 방법은, 가장 큰 점수의 턴들부터 먹는 것이다. i + (i-1) + (i-2) + … + (i-k) + c = x, (0≤ c < i-k) 가 되도록 x 를 써주면 된다. 이렇게 썼을때의 항의 갯수가 답이 된다.
- 첫번째 식과 두번째 식을 계산하는 가장 간단한 방법은, 그냥 루프를 돌면서 계산하는 것이다. 최대 턴 수는 O(sqrt(x+y))기 때문에 이렇게 해도 충분히 계산이 가능하다. 좀더 속도를 높이고 싶으면, 이분탐색을 써서 O(log(sqrt(x+y))로 줄이거나, 아니면 그냥 위의 수식을 이차방정식으로 정리하고 그냥 일반해를 구해서 O(1)에 계산해버릴수도 있다.
코드
"""Solution code for "BOJ 12934. 턴 게임".
- Problem link: https://www.acmicpc.net/problem/12934
- Solution link: http://www.teferi.net/ps/problems/boj/12934
Tags: [Greedy]
"""
import math
def main():
x, y = [int(x) for x in input().split()]
max_turn = (math.isqrt(8 * (x + y) + 1) - 1) // 2
if (max_turn + 1) * max_turn // 2 != x + y:
answer = -1
elif x == 0:
answer = 0
else:
t = max_turn * 2 - 1
answer = math.ceil((t - (t * t + 8 * (max_turn - x))**0.5) / 2) + 1
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/12934.txt · 마지막으로 수정됨: 2022/02/02 05:39 저자 teferi
토론