[알고리즘] 백준 12934번 문제 - 턴 게임 (그리디)

date

Nov 27, 2023

slug

al-13

author

status

Public

문제

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

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

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

입력

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

출력

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

예제 입력 1


7 14

예제 출력 1

예제 입력 2


10 0

예제 출력 2

예제 입력 3


932599670050 67400241741

예제 출력 3

예제 입력 4


7 13

예제 출력 4

-1

힌트

윤호가 1, 2, 4 턴을 이기고, 동혁이가 3, 5, 6 턴을 이겼다면 가능한 결과이다. 윤호의 승리 횟수가 최소가 되는 경우는 윤호가 1, 6 턴을 이기고, 동혁이가 2, 3, 4, 5를 이긴 것이다.

코드


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

if x == 0 and y == 0:
    print(0)
else:
    k = 1
    possible = True
    while True:
        # x와 y의 합이 1 ~ K까지의 합이라면 가능한 경우
        if x + y == k * (k + 1) // 2:
            break
        # 1 ~ K까지의 합이 아니라면 가능하지 않은 경우
        if x + y < k * (k + 1) // 2:
            possible = False
            break
        k += 1

    if not possible:
        print(-1)
    else:
        result = 0
        for i in range(k, 0, -1):
            if x == 0:
                break
            x -= min(x, i)
            result += 1
        print(result)

설명

이 문제를 해결하기 위한 주요 로직은 두 사람이 이긴 횟수의 합이 x와 y의 합이 되는 경우를 찾는 것입니다. 이를 위해 우리는 두 사람이 이긴 횟수를 1부터 증가시키며 이긴 횟수의 합이 x와 y의 합과 같아지는지 확인합니다.

코드는 먼저 두 사람이 이긴 횟수를 나타내는 변수 k를 1로 초기화하고, 가능한 경우를 나타내는 변수 possible을 True로 설정합니다.

반복문은 두 가지 경우에 break로 종료됩니다.

x와 y의 합이 1부터 k까지의 합과 같을 경우: 이 경우는 두 사람이 이긴 횟수의 합이 x와 y의 합과 같아지는 경우입니다. 이 경우는 윤호와 동혁이의 점수가 각각 x와 y가 될 수 있는 경우입니다.

x와 y의 합이 1부터 k까지의 합보다 작을 경우: 이 경우는 두 사람이 이긴 횟수의 합이 x와 y의 합보다 크게 되는 경우로, 이 경우는 윤호와 동혁이의 점수가 각각 x와 y가 될 수 없는 경우입니다.

반복문이 종료된 후에는 possible 변수를 확인하여, 만약 possible이 False라면 -1을 출력하고, 그렇지 않다면 윤호가 이긴 횟수를 계산합니다. 윤호가 이긴 횟수를 계산하기 위해 k부터 1까지 반복하며, 윤호가 이길 수 있는 최대 횟수를 x에서 빼고, 이긴 횟수를 1 증가시킵니다. 이 과정을 x가 0이 될 때까지 반복합니다.

마지막으로 윤호가 이긴 횟수를 출력합니다. 이 코드는 윤호가 이긴 횟수를 최소로 하면서, 윤호의 점수가 x, 동혁의 점수가 y가 되는 경우를 찾는 알고리즘을 구현한 것입니다.