[파이썬/python] 백준 - 12934 턴 게임

문제

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

---

문제 설명

1. 각 턴으로 이루어진 게임이 존재한다.
   1. 턴은 1턴부터 시작해서 n턴까지 이루어져 있다.
   2. i턴의 승자에게 i점의 점수가 부여된다.
2. 윤호와 동혁이의 점수 x와 y가 주어진다.
3. 게임을 진행했을 때 윤호가 x점, 동혁이가y점이 될 수 있는지 판별한다.
   1. 게임이 가능하다면 윤호가 최소 몇 번 이겨야 하는지도 구한다.

 

---

풀이

1. x와 y의 최대 값은 $10^{12}$이다.
   1. 나올 수 있는 최댓 값 $x=$ $10^{12}$ , $y=$ $10^{12}$ 일 때를 기준으로 현재 점수가 진행 가능한 게임인지 판별한다.
   2. 불가능하다면 -1을 출력한다.
2. 게임 진행이 가능하다면 진행 가능한 최대 턴 수를 구한다.
3. 게임을 이겨야 하는 최소 횟수를 구한다.(n턴)
   1. 최소 횟수가 되기 위해서는 n부터 1까지 x가 될 때까지 큰 수부터 차례대로 더한다.

 

---

코드

import sys
x,y = map(int,input().split())

MAX_SIZE = (10**12)*2
max_count = 0

num = 0
make = 0 
for i in range(1, MAX_SIZE+1):
    if num == (x + y):
        make = 1
        break
    if num + i > MAX_SIZE:
        break
    max_count += 1
    num += i
if not make:
    print(-1)
else:
    res = 0
    cnt = 0
    for i in range(max_count, 0,-1):
        if res + i <= x:
            res += i
            cnt += 1
        if res == x:
            break
    print(cnt)

---

시간복잡도

• 최대 진행 가능 한 턴을 구할 때 최댓값인 $x=$ $10^{12}$ , $y=$ $10^{12}$일 때 총 1999999회, 즉 $O(10^6)$ 정도의 시간복잡도가 소요된다.
• 최소 몇 번 이겨야 할 지 계산할 때도 최댓값인 $10^6$회를 모두 탐색한다고 한다면 마찬가지로 $O(10^6)$ 정도의 시간복잡도가 소요된다.
  
• 따라서 약 $O(10^6)$의 시간복잡도를 가진다.