백준 6064번: 카잉 달력

문제 이해를 위해 M=10, N=12, x=3, y=1 인 경우, 카잉 달력 세는 법을 예시로 보자

• 첫 번째 해: <1:1>
• 두 번째 해: <2:2>
• 세 번째 해: <3:3>
• 네 번째 해: <4:4>
• 다섯 번째 해: <5:5>
• 여섯 번째 해: <6:6>
• 일곱 번째 해: <7:7>
• 여덟 번째 해: <8:8>
• 아홉 번째 해: <9:9>
• 열 번째 해: <10:10>
• 열한 번째 해: <1:11> (x가 M에 도달하여 다시 1로 돌아감)
• 열두 번째 해: <2:12>
• 열세 번째 해: <3:1> (y가 N에 도달하여 다시 1로 돌아감)

위와 같이 M=10, N=12, x=3, y=1인 경우 정답은 13이다.

 

M=10, N=12, x=3, y=9인 경우

• 첫 번째 해: <1:1>
• 두 번째 해: <2:2>
• 세 번째 해: <3:3>
• 네 번째 해: <4:4>
• 다섯 번째 해: <5:5>
• 여섯 번째 해: <6:6>
• 일곱 번째 해: <7:7>
• 여덟 번째 해: <8:8>
• 아홉 번째 해: <9:9>
• 열 번째 해: <10:10>
• 열한 번째 해: <1:11>
• 열두 번째 해: <2:12>
• 열세 번째 해: <3:1>
• 열네 번째 해: <4:2>
• 열다섯 번째 해: <5:3>
• 열여섯 번째 해: <6:4>
• 열일곱 번째 해: <7:5>
• 열여덟 번째 해: <8:6>
• 열아홉 번째 해: <9:7>
• 스무 번째 해: <10:8>
• 스물한 번째 해: <1:9>
• 스물두 번째 해: <2:10>
• 스물세 번째 해: <3:11>
• 스물네 번째 해: <4:12>
• 스물다섯 번째 해: <5:1>
• 스물여섯 번째 해: <6:2>
• 스물일곱 번째 해: <7:3>
• 스물여덟 번째 해: <8:4>
• 스물아홉 번째 해: <9:5>
• 서른 번째 해: <10:6>
• 서른한 번째 해: <1:7>
• 서른두 번째 해: <2:8>
• 서른세 번째 해: <3:9>

로 정답은 33이다.

 

여기서 알 수 있는 것은, M=10, N=12, x=3, y=9 일 때 x=3인 경우만 보면 된다는 것이다.
즉, x+m만큼 건너뛰면서 y의 값이 9인지 살피면 되는 것이다.

이 예제의 <x:y>에서 x는 10진수, y는 12진수라고 생각하면 쉽다.
x번째의 y값으로는 x를 12로 나눈 나머지 값이 오게 된다.

즉 반복문에서 i를  x + m만큼 증가시키며 반복할 때, i % n == y일 때 정답인 것이다.

 

여기서 주의 할 점은 나머지 계산으로 값을 구하게되면 0을 포함시키게 된다는 것이다.
예를 들어, input M=10, N=12, x=2, y=12일 때

• 첫 번째 해: <1:1>
• 두 번째 해: <2:2>
• 세 번째 해: <3:3>
• 네 번째 해: <4:4>
• 다섯 번째 해: <5:5>
• 여섯 번째 해: <6:6>
• 일곱 번째 해: <7:7>
• 여덟 번째 해: <8:8>
• 아홉 번째 해: <9:9>
• 열 번째 해: <10:10>
• 열한 번째 해: <1:11>
• 열두 번째 해: <2:12>

로 정답이 12가 되어야 하지만, i % n을 수행하면 12 % 12 = 0이 되어, 12가 아니므로 답을 찾게되지 못한다.
이 것은 1-based를 0-based로 조정하여 해결할 수 있다.
처음에 x, y값을 각각 1씩 빼고 시작한 뒤, 마지막 결과값에 다시 1을 더해주면 된다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < t; i++) {
			// 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			int result = kaingCalandar(m, n, x, y);
			sb.append(result + "\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	// 카잉 달력 계산
	private static int kaingCalandar(int m, int n, int x, int y) {
		x--; // 1-based를 0-based로 조정
		y--; // 1-based를 0-based로 조정
		for (int i = x; i < m * n; i += m) {
			if (i % n == y) {
				return i + 1; // 0-based에서 다시 1-based로 변환
			}
		}
		return -1;
	}
}