6064번. 카잉 달력

 

 

아이디어

<1:1> 에서 시작해서 <x:y> 가 되는 해가 언제인지를 단순한 브루트포스 방식으로 탐색하려 했으나 시간초과가 발생했다.

 

따라서 다른 방법이 필요했고 'x - y' 값을 활용하는 방식을 선택했다.

카잉 달력은 처음에는 <1:1> 과 같이 두 값의 차가 0 인 상태에서 시작하지만 둘 중 한 쪽이 한계치에 도달해서 다음 값이 1이 되는 순간 두 값의 차가 바뀌게 된다.

 

이 점을 활용해서 두 값의 차가 'x - y' 와 같아지는 순간을 찾고 그 지점에서 <x:y> 까지 얼마나 더 지나야 하는지를 알아내면 된다.

 

예를 들어 <3:9> 의 경우

<1:1> : 1번째

<1:11> : 11번째

<3:1> : 13번째

<1:9> : 21번째

<5:1> : 25번째

<1:7> : 31번째

 

에서 차가 'x - y' 와 같이지게 되고 31번째가 <1:7> 인데 목표는 <3:9> 이니 31 + (3 - 1) 해서 33번째가 정답이 된다.

 

<M:N> 이 카잉 달력의 마지막 해이므로

두 값의 차가 'M - N' 과 같아지는 시점 이후로는 더 탐색을 할 필요가 없다.

 

풀이코드

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 {
        StringBuilder sb = new StringBuilder();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        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 targetDiff = x - y;

            int a = 1;
            int b = 1;
            int cnt = 1;
            int diff = a - b;

            while (diff != targetDiff && diff != M - N) {
                if (M - a < N - b) {
                    cnt += M - a + 1;
                    b += M - a + 1;
                    a = 1;
                } else {
                    cnt += N - b + 1;
                    a += N - b + 1;
                    b = 1;
                }
                diff = a - b;
            }

            if (diff != targetDiff) {
                sb.append(-1);
            } else {
                cnt += x - a;
                sb.append(cnt);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}