https://www.acmicpc.net/problem/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))
'Algorithm > Algorithm Problem' 카테고리의 다른 글
백준 15649,15650 N과 M(Backtracking) (0) | 2021.11.21 |
---|---|
백준 1931 회의실 배정 (0) | 2021.11.16 |
백준 17427 약수의 합2 (0) | 2021.11.02 |
##백준 15990 1, 2, 3 더하기5 (0) | 2021.10.29 |
백준 11052 카드 구매하기 (0) | 2021.10.29 |