BOJ-10837 동전 게임

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

문제 소개

게임의 라운드 수 k가 주어졌을 때, 입력되는 m, n이 영희와 동수의 점수가 될 수 있는지 판별하는 문제이다.

문제 풀이

아래와 같이 세 경우로 나누어 생각한다. 주어진 m과 n이 가능한 점수이려면 점수가 m, n이 되기 전의 이전 점수가 문제의 3번 규칙을 만족해야 한다. 3번 규칙을 만족하지 못한다면 게임이 바로 끝나게 되어 점수가 m, n이 되지 못하기 때문이다.

1. m과 n이 같은 경우 : 영희와 동수 둘 중 한명만 득점하는 라운드가 없음을 의미하므로 1을 반환한다.

2. m이 n보다 큰 경우 : 이전 점수에서의 (m과 n의 차이) > (동수의 남은 기회)라면 0을 반환하고 그렇지 않다면 1을 반환한다.

3. m이 n보다 작은 경우 : 이전 점수에서의 (m과 n의 차이) > (영희의 남은 기회)라면 0을 반환하고 그렇지 않다면 1을 반환한다.

2번과 3번 경우 이전 점수에서의 (m과 n의 차이)는 (max(m, n) - 1) - min(m, n)으로 같다.

매 라운드 항상 영희가 먼저 동전을 던지므로 (동수의 남은 기회)와 (영희의 남은 기회)는 조금 달라진다.

• (동수의 남은 기회) : 영희의 점수가 m으로 갱신되는 순간은 라운드가 진행 중이다. 동수는 최대 k - (m - 1)번의 기회를 갖는다. 영희가 점수 m을 얻은 라운드에 동수도 점수를 1점 얻을 수 있는 가능성이 있기 때문이다.

• (영희의 남은 기회) : 동수의 점수가 n으로 갱신되며 라운드가 끝난다. 그리고 영희는 최대 k - n번의 기회를 갖는다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()


def score(m, n):
    if m == n:
        return 1
    elif m > n:
        if (m - 1) - n > k - (m - 1):
            return 0
        else:
            return 1
    else:   # m < n
        if (n - 1) - m > k - n:
            return 0
        else:
            return 1


k = int(input())
c = int(input())
for _ in range(c):
    m, n = map(int, input().split())
    print(score(m, n))