[Silver I] 카잉 달력 - 6064

문제 링크

성능 요약

메모리: 18024 KB, 시간: 348 ms

분류

브루트포스 알고리즘, 중국인의 나머지 정리, 수학, 정수론

제출 일자

2024년 5월 14일 14:32:10

풀이

너무나 당연스러울 정도로 while문을 생각했지만, 입력 데이터 값과 시간을 보고 절대 while문으로 하나하나 찾는 것은 아닐 것이라 생각했다.

근데 그 이후엔 어떻게 해야 할 지 감이 오지 않아서 다른 분들의 블로그를 참고했다...

참고
[Tistory - 카잉달력]
[Velog - 카잉달력]

참고 내용
ex M=5, N=7
1: <1,1> 6: <1,6> 11<1,4> 16<1,2> 21<1,7> 26<1,5> 31<1,3>
2: <2,2> 7: <2,7> 12<2,5> 17<2,3> 22<2,1> 27<2,6> 32<2,4>
3: <3,3> 8: <3,1> 13<3,6> 18<3,4> 23<3,2> 28<3,7> 33<3,5>
4: <4,4> 9: <4,2> 14<4,7> 19<4,5> 24<4,3> 29<4,1> 34<4,6>
5: <5,5> 10:<5,3> 15<5,1> 20<5,6> 25<5,4> 30<5,2> 35<5,7>
위와 같이 M=5, N=7 이면은 x 기준으로 M번 째일때마다 x 는 그대로고 y값만 바뀐다. 그러므로
반복 for문을 for (int i = x; i < (m n); i += m) 으로 주었다.
우리는 < x, y > 가 몇번째인지 구해야하므로 i = x 로 시작한다.
최대 M N = 35 개가 나올 수있으므로 최대 35까지 돌린다.
i+=m 에서 x는 m만큼 더해줘도 그대로이므로 m만큼 + 해준다
if (i % n == y) { 조건을 걸어주어서 y 의 최대반복인 n만큼 % 해준다.
우리가 구할 y 값이나오면 break;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int M,N;
		int x,y;
		boolean check= false; //<x:y>가 유효하지 않은 표현인지 아닌지 확인
		
		int num = Integer.parseInt(br.readLine());
		
		for (int j=0; j<num; j++) {
			st= new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken())-1; // 나눗셈 연산이 0일 수있기때문에 -1 해준다.
			y = Integer.parseInt(st.nextToken())-1; // 나눗셈 연산이 0일 수있기때문에 -1 해준다.
			
			for (int i=x; i<(M*N); i+=M) {
				if(i % N ==y) {
					System.out.println(i+1);
					check= true;
					break;
				}
			}
			if(!check) {//만약 유효한 표현이 아니라면
				System.out.println(-1);
			}
			check=false;	
		}
	}
}