P6064. 카잉 달력

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

6064번: 카잉 달력

설명

1️⃣ 번째 풀이

x, y에 도달할 때까지, 모든 경우의 수를 계산하여 시간초과가 발생했다. 

 

2️⃣ 번째 풀이

나머지가 0인 경우를 찾아 풀이한다. 

예를들어, k=33이라면 m,n,x,y는 10, 12, 3, 9로 주어졌다.

- 33에서 x를 빼고 m으로 나눈 것: (33-3) % 10 = 0

- 33에서 y를 빼고 n으로 나눈 것: (33-9) % 12 = 0

=> 모두 나머지가 0이다. 

 

즉 x, y에 각각 m, n을 적절히 더해 k를 만든다. 

적절히 더하는 것은 나누어도 나머지가 0이 되어야 한다.

 

x에 m을 더해가면서 k를 만들고, 만든 k에서 y를 빼서 n으로 나눠떨어지는지 확인한다. 

 

x=3, m=10인 상황에서

1회차

- x = 13 + 10 = 23이 된다.

- y를 뺀 값 23 - 9 = 14는 12로 나누어 떨어지지 않는다.

 

2회차

- x = 23 + 10 = 33이 된다.

- y를 뺀 값 33 -9 = 24로 n=12로 나눠 떨어진다.

=> 33이 답이 된다.⚡️

x는 k가 되므로, 바로 x를 반환한다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int T, M, N, x, y;
    static String arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            arr = br.readLine().split(" ");
            M = Integer.parseInt(arr[0]);
            N = Integer.parseInt(arr[1]);
            x = Integer.parseInt(arr[2]);
            y = Integer.parseInt(arr[3]);

            sb.append(calendar(M, N, x, y)).append("\n");
        }

        System.out.println(sb);
    }

    static int calendar(int M, int N, int x, int y) {
        while (x <= M * N) {
            if ((x - y) % N == 0) {
                return x;
            }
            x += M;
        }
        return -1;
    }
}

 

Reference

https://chanmuzi.tistory.com/8