[백준/12966] 턴 게임 (Python)

Problem : https://www.acmicpc.net/problem/12966

12966번: 턴 게임 2

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:29:46

 

---

 

문제 설명

 

 

윤호와 동혁이는 BOJ 알고리즘 캠프에 참가중이다. 두 사람은 문제가 너무 안 풀릴 때는 게임을 하고 문제를 풀기도 한다.

게임은 턴으로 이루어져 있으며, 각 턴의 승자는 두 사람 중에 한 사람이다. i번째 턴을 승리한 사람은 점수 2×i-1점을 갖게 되고, 턴은 1부터 시작한다.

두 정수 x와 y가 주어졌을 때, 윤호의 점수가 x, 동혁이의 점수가 y가 되는 것이 가능한지 불가능한지 구하는 프로그램을 작성하시오. 만약, 가능하다면 윤호가 최소 몇 번 이겨야 하는지도 구하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 두 정수 x와 y가 주어진다. (0 ≤ x, y ≤ 10^12)

 

출력

 

윤호가 최소 몇 번 이겨야 하는지 출력한다. 불가능한 경우에는 -1을 출력한다.

 

입력 예시

 

8 17

 

출력 예시

 

2

 

 

---

 

풀이

 

조건을 잘 보면, 점수는 모두 홀수로 주어진다는 사실을 알 수 있다. 그리고 1부터 2*i-1까지의 모든 홀수의 합은 제곱수, 즉 i^2가 된다.

 

따라서 (x+y)값이 제곱수인지를 판단한다면 대부분의 경우를 가지치기할 수 있다.

 

또한 x 조합으로 가장 작은 조합을 찾으려면, 그리디하게 들어갈 수 있는 가장 큰 홀수부터 넣어 보면 된다. 여기서 주의할 점은, 남는 x == 2인 경우는 존재가 불가능하다. (2보다 작은 홀수는 1이며, 1 하나로는 2를 표현할 수 없다) 이 점을 염두해 두고 문제를 풀이하도록 하자.

 

풀이 코드

MAX = float('inf')
x, y = map(int, input().split())
total = x + y
if total ** 0.5 % 1 != 0 :
  print(-1)
  exit()
if x == 0 :
  print(0)
  exit()
total = int(total ** 0.5)
cnt = 0

for i in range(total-1, -1, -1) :
  if x < 2*i+1 or x - 2*i - 1 == 2 :
    continue
  x -= 2*i + 1
  cnt += 1
  if x == 0 :
    break
print(cnt if not x else -1)

풀이 완료!