제로베이스 20220510 코테 연습

1. 카잉 달력

• 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다.
• 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다.
• 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다.
• 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다.
• 같은 방식으로 만일 y < N이면 y’ = y + 1이고, 그렇지 않으면 y’ = 1이다.
• 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.
• 예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다.

• <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

• 네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력

• 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
• 각 테스트 데이터는 한 줄로 구성된다.
• 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

출력

• 출력은 표준 출력을 사용한다.
• 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다.
• 여기서 k는 가 k번째 해를 나타내는 것을 의미한다.
• 만일 에 의해 표현되는 해가 없다면, 즉, 가 유효하지 않은 표현이면, -1을 출력한다.

풀이

import sys

T = int(sys.stdin.readline())

for _ in range(0, T):
    M, N, x, y = list(map(int, sys.stdin.readline().split()))

    mon_cycle = [x + k * M for k in range(0, N) if x + k * M < (M * N) + 1]
    day_cycle = {y + k * N:0 for k in range(0, M) if y + k * N < (M * N) + 1}

    flag = False
    for p in mon_cycle:
        if p in day_cycle:
            flag = True
            print(p)
            break
    if not flag:
        print(-1)

채점 결과

• 정답

리뷰

• 달에 x가 오는경우는 x+k*M 번 날, 일에 y가 오는 경우는 y+k*N번 날이므로, 두 인덱스의 집합에서 공통된 날짜를 추출하면 정답일것으로 예측했고, 실제로 예시문제는 전부 맞았다.

• 하지만 시간복잡도를 계산해보면 알수 있듯이, 대충 $O(2N+N^{2})$쯤 되어보이는 답없는 코드이고, 실제로도 pypy를 써서야 간신히 시간을 맞추는 코드이기에, 실질적으로는 오답으로 봐야한다.

더 나은 풀이

• 풀이 출처 : 아이디 wider93님의 풀이

import sys
def euc(x, y):
    q = []
    while y:
        q.append(x // y)
        x, y = y, x % y
    q.pop()
    a, b = 0, 1
    for i in q[::-1]:
        a, b = b, a - i*b
    return x, a, b


def f():
    M, N, x, y = [int(i) for i in sys.stdin.readline().split()]
    d = x-y

    g, a, b = euc(M, N)
    if d % g:
        return -1
    k = d // g
    K = x - k*a*M
    return (K-1) % (M//g*N) + 1


for _ in range(int(sys.stdin.readline())):
    print(f())

더 나은 풀이 리뷰

• 예전 풀이도 그렇고(체스판 다시 칠하기) 이분 풀이는 볼때마다 벽을 느끼게 되는것 같다.

• 프로그램 흐름대로 해석해보면, 메인함수 -> f() -> euc()순서이므로, 해당 순서대로 해석한다.

• 메인 함수
  • 테스트 케이스 개수 T를 sys.stdin.readline()으로 받고, 매 케이스에 대해 f()함수의 결과를 출력한다.
• f()
  • 테스트 케이스에서 주어진 수에 대해 입력받는다.
    • 내가 늘 쓰던 map함수를 통한 방식이 아니라서 새롭다.
    • 번외 - map함수 vs list comprehension 속도 관련 스택 오버플로우
      • 결론만 말하자면, 입력받는 데이터 크기를 완전히 모를경우 map함수의 오버헤드가 커져 성능상의 문제가 생길수 있다고 한다.
      • 단, 복잡한 함수일수록 이러한 오버헤드 차이는 무시할만한 정도라고 한다.
      • 다만, 파이썬의 창시자 귀도 반 로섬은 map함수와 filter함수를 python3에서 삭제해버리고 싶을정도로 싫어했다고 한다.참고 링크 - 귀도 반 로섬의 블로그
• 이번 문제도 시일을 두고 해석해야 할것 같다.
  • 현재까지 알아낸건, 곱셈의 역원과 관련하여 페르마의 소정리 및 확장 유클리드 호제법에서 나오는 수식과 비슷해보이는 구석이 약간 있다.
  • 이번 문제에서 요구하는 알고리즘인 중국인의 나머지 정리가 해당 개념을 요구하며, 이 문제는 정수론의 개념과 맞닿아있다고 한다.
  • 대학수학도 못배운 내가 하루만에 이해할 내용은 아닌거같으니, 시일을 두고 차근차근 해석해보자.