사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
Z C D O O
 
ps/problems/boj/12934.txt · 마지막으로 수정됨: 2022/02/02 05:39 저자 teferi