문제

영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:

1. 한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다.

2. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오 면 점수를 얻지 못한다.

3. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시 점에서도 게임은 바로 끝난다.

0이상 K이하인 임의의 정수 M과 N에 대해서, 이것 이 항상 게임이 끝난 후 영희와 동수가 얻는 점수가 되 는 것은 아니다.

예를 들어서, K=2인 경우에, M과 N의 모든 경우에 대해서, 이것이 영희와 동수가 얻는 점수가 될 수 있는 지의 여부는 다음 표와 같다:

M N 영희, 동수의 점수가 될 가능성
0 0 가능
0 1 가능
0 2 불가능
1 0 가능
1 1 가능
1 2 가능
2 0 가능
2 1 가능
2 2 가능
위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불 가능한 이유는 두 번째 라운드에서 영희가 뒷면이 나와 서 점수를 얻지 못하는 순간 게임의 규칙 3에 의해서 0 과 1로 게임이 끝나기 때문이다.

0이상 K이하인 정수 M과 N이 주어질 때, 이 두 정 수가 각각 영희와 동수의 점수가 될 수 있는지 여부를 판별하는 프로그램을 작성하시오

입력

첫 줄에 게임의 라운드 수를 나타내는 정수 K(1≤K≤1,000)가 주어진다.

두 번째 줄에는 입력의 개수를 나타내는 정수 C(1≤C≤100,000)가 주어진다.

다음 이어지는 C개의 줄 각각에는 하나의 입력을 나타내는 두 정수 M과 N(0≤M,N≤K)이 주어진다.

입력 예시

5
4
5 5
5 1
0 3
1 4

출력

출 력은 C개의 줄로 구성된다. 게임에서 영 희와 동수의 점수가 각각 M과 N이 될 수 있다면 1, 아니면 0을 각 줄에 출력한 다

출력 예시

1
0
1
0

문제 풀이

문제를 풀기는 했는데, 시간을 어떻게 줄여야 할 지 모르겠다.
일단 정답처리는 되는데 시간이 너무 오래걸려서 추가적으로 고민을 더 해봐야한다.

해당 문제를 풀 때 처음에 이해가 살짝 안가서 하나씩 대입해보면서 규칙을 확인했다.

# 라운드 수
K = int(input())

# 점수 개수
C = int(input())

# 점수 리스트
grade = []
for i in range(C):
    M,N = map(int,input().split(" "))
    grade.append([M,N])

# 나올 수 있는 점수인 경우에는 1, 나올 수 없는 경우에는 0
# 영희의 점수는 grade[0], 동수의 점수는 grade[1]

def chk_grade(grade,K):

    remain_round = K - max(grade)
    gap = abs(grade[0] - grade[1])

    # 영희와 동수의 점수가 같은 경우는 무조건 나올 수 있는 case
    if grade[0] == grade[1]:
        return 1
    # 영희의 점수가 더 높은 경우 (영희의 순서가 선)
    elif grade[0] > grade[1]:
        if (gap - remain_round) <= 2:
            return 1
        else:
            return 0
    # 동수의 점수가 더 높은 경우
    else:
        if (gap - remain_round) <= 1:
            return 1
        else:
            return 0
result_ary = []
for i in range(C):
    result_ary.append(chk_grade(grade[i],K))

for i in range(C):
    print(result_ary[i])