백준 6064 카잉 달력

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

6064번: 카잉 달력

import sys

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

for _ in range(num):
    m,n,x,y = map(int,sys.stdin.readline().split())
    cnt = 0
    i = 0
    j = 0

    while True:
        if i < m and j < n:
            i += 1
            j += 1
            cnt += 1
        elif i == m:
            i = 1
            j += 1
            cnt += 1
        elif j == n:
            i += 1
            j = 1
            cnt += 1
        else:
            print(-1)
            break
        if i == x and j == y:
            print(cnt)
            break

처음에 하나씩 증가 시키면서 찾았다가 바로 시간초과 나버려서 효과적으로 풀 수 있는 방법을 찾아야했다.

 

 

일정 크기 이상이 되어 다시 1이나 0으로 초기화되는 수법 ==> 나머지 연산이랑 똑같은 원리

 

즉, x나 y에서 m이나n만큼 일정하게 더해서 나머지연산을 해도 똑같이 x,y가 된다.

 

이 방식이 왜 중요한가

위의 코드처럼 1씩 더해서 모든 경우를 고려하게되면 매우 느림

하지만 1이 아닌 m,n처럼 간격을 크게 하면 테스트 케이스를 줄일 수 있게 된다.

 

ex) 10 12 3 9로 해보자.

<1,1>로 시작하는 날짜가 <3,9>에 멈추는 count를 구하는 것이다.

먼저 x가 3이 되려면, 3, 3+10, 3+10+10, 3+10+10+10번째 count에 될 것이고

y가 9이 되려면 9, 9+12, 9+12+12, 9+12+12+12번째 count에 될 것이다.

 

이 2가지 모두 같은 상황을 고려하려면 어떻게 하면될까?

하나를 고정해놓고 똑같은 count가 만들어질때를 노리면 된다.

 

y를 고정해놓고 x+=m만큼 증가시켜보자.

 

x+=m시킨 <x,y>가 실제 테스트 케이스에서 나올 수 있는지 없는지를 확인하기 위한 과정으로

 

y는 이미 고정되었기 때문에 n에 대한 나머지는 9가 항상 나올 것이다.

y의 나머지가 9라는건 9만큼의 턴을 썻다고 이해하면 되기때문에 x%n했을때 9인 경우를 캐치하면 된다.

 

즉, x%n == y%n 일때를 구하면 된다.

 

why) x%m이 아니냐면 x==m이 될때마다 1로 초기화를 시켜주는게 아닌 x+=m을 하면서 y%n과 맞는 테스트 케이스를 찾고 있는 것이기 때문

import sys

def fun(m, n, x, y):
    while x <= m * n:
        if x%n == y%n:
            return x
        x += m
    return -1

num = int(input())
for _ in range(num):
    m, n, x, y = map(int, sys.stdin.readline().split())
    print(fun(m, n, x, y))