[BOJ] 6064번 - 카잉 달력

---

문제설명

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

6064번: 카잉 달력

사고과정

• 처음에 while문으로 하려했으나 시간초과가 발생할 뿐만 아니라 유효하지 않은 경우의 수를 필터링하지 못했다. 그래서 힌트를 보고 DP를 활용해 구현하려 했지만 이것도 모든 테스트를 통과하지 못했다..
• 그래서 풀이를 보았는데, 특정 규칙을 찾는 것이 관건이었다. 이 규칙을 찾기 위해서는 "하나만 생각" 하고 "원형 리스트"를 생각하면 될 것 같았다. 여기서 원형 리스트란 무엇이냐? 바로 %(나머지 연산)을 사용해서 다시 리스트 인덱스 앞으로 이동하는 것을 말한다. 예를 들어, [1,2,3,4] 가 있을 때, 인덱스가 5번이라고 한다면 값을 넘어가기 때문에 다시 초기화해서 돌아가야 한다. 이 때 5 % 4(리스트 길이)를 하게 되면 1이 되는데 이는 곧 1번 인덱스를 의미한다. 이와 비슷하게 이 문제에도 적용할 수 있는 듯 했다.
• 우선 x, y가 다시 1로 돌아가는 조건인 M, N이 주어졌다. 따라서 x, y가 M, N보다 커질 때 1로 회귀하는데, 이 때 %연산자를 활용한다.
• 그리고 x는 어차피 M을 계속 더해도 M보다 커지면 다시 1로 회귀하게 된다. 따라서 x를 고정시키고 y와 y의 범위인 N을 활용할 수 있다.
• 예를 들어, M = 10, N = 12, x = 3, y = 9 라고 할 때, x인 3을 N인 12로 나머지 연산을 한 값과 y인 9와 N인 12를 나머지한 연산 결과값이 같다면 그 때의 x 값이 바로 정답을 의미한다. 이 때, 나머지 한 연산 결과값이 서로 다를 때마다 x에다가 x의 범위인 M을 더해준다. 그래야 x가 1로 회귀하는 동안 증가한 해(year)를 셀 수 있기 때문이다.
• 뭔가 수학문제를 푸는 것 같았다. 상당히 어렵다..

풀이(스스로 못 푼 풀이)

import sys
input = sys.stdin.readline
for tc in range(int(input())):
    m, n, x, y = map(int, input().split())
    flag = True
    while x <= n*m:
        if x % n == y % n:
            print(x)
            flag = False
            break
        x += m
    if flag:
        print(-1)