[python] 백준 6064 - 카잉달력

백준 6064 - 카잉달력 [SILVER 1]

리버스 잉카 문명의 달력이다 엌

문제

이딴 달력을 쓰니까 망했지…라고 하기엔 우리나라도 비슷한 게 있다…

M과 N보다 작거나 같은 자연수로 연도를 <x, y>와 같이 표현한다.

우리나라가 당해의 이름을 정할 때와 같은 방식이다.

갑을병정… 등의 십간(十干)과 자축인묘… 등의 십이지신(十二支神)을 사용하는 것이다.

2024년인 올해는 갑진년 청룡의 해다.

갑은 십간의 첫 번째, 진은 십이지신의 다섯 번째

이번 문제로 표현하면, <1, 5>가 되는 것이다.

마찬가지로 계해년 - <10, 12>가 되면, 내년부턴 다시 <1, 1>로 돌아간다.

값은 똑같이 증가하나, x는 M진법, y는 N진법을 쓴다고 보면 되겠다.

정확히는 1부터 시작하여 M과 N까지 이르는 방식이기 때문에 엄밀히 말하면 진법은 아니지만.

어쨌든 이 패턴에 따라 주어진 <x, y>는 <1, 1> 부터 몇 번째 해인지 알아내는 것 문제다.

만약 유효하지 않은 수라면 -1을 출력하면 된다.

수학 문제인 것 같다.

접근 방법

<x, y> 가 목표이고, 각 진법을 풀어 자연수로 표현한 수가 Y라 하자.

M = 10, x = 3이라 가정한다면, 가능한 수는 3 또는 3 + (10 * n) 뿐이다.

x가 만족할 수 있는 Y 값의 리스트는 [3, 13, 23, 33, 43...]이다.

여기서 N = 12, y = 9 로 가정하자.

변수 y에 할당될 수는 Y를 N으로 나눈 나머지다.

즉, x를 만족하는 값이 들어있는 리스트를 순회하며,

해당 값을 N으로 나눈 나머지가 9가 된다면 정답이 나오게 된다.

코드로 만든다면 다음과 같다.

if x % N == y:
    print(x)

다만 여기서 주의해야 할 점이 하나 있는데,

M = 8, N = 16, x = 8, y = 16 와 같은 값이 들어왔을 때,

위의 조건문은 사용할 수 없게 된다.

16에 도달했을 때, 나머지로 16을 반환해야 하는데

16 % 16이므로 당연히 0이 나온다.

이는 N과 y가 같은 값일 때 등장하는 케이스로, 이에 대한 조건문을 추가해주면 끝이다.

if x % N  == y or (N == y and x % N == 0)

이제 코드를 실행시켜보자.

ㅋㅋㅋㅋㅋㅋㅋㅋ

정답 코드

import sys

input = sys.stdin.readline

for t in range(int(input())):
    
    M, N, x, y = map(int, input().split())
        
    n = x
    while n <= M*N:
        if n%N == y or (N == y and n%N == 0):
            print(n)
            break
        n += M
        
    else:
        print(-1)