알고리즘 단계별로 풀어보기 : BOJ-6064(카잉달력)

문제(출처)

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 

카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 

그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 

그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 

<x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 

같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 

<M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 

첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. 

<3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 

입력은 T개의 테스트 데이터로 구성된다. 

입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 

각 테스트 데이터는 한 줄로 구성된다. 

각 줄에는 네 개의 정수 M, N, x와 y가 주어진다.

(1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 

각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 

여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 

만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

예제 입력

3

10 12 3 9

10 12 7 2

13 11 5 6

예제 출력

33

-1

83

내 풀이

package date_20181224;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

public class BOJ_6064 {

    public static void main(String args[]) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        try {

            int num = Integer.parseInt(br.readLine());

            int result = 0;

            for (int i = 0; i < num; i++) {

                String[] arrStr = br.readLine().split(" ");

                int m = Integer.parseInt(arrStr[0]);

                int n = Integer.parseInt(arrStr[1]);

                int x = Integer.parseInt(arrStr[2]);

                int y = Integer.parseInt(arrStr[3]);

                result = calc(m, n, x, y);

                bw.write(String.valueOf(result));

                bw.newLine();

            }

            bw.flush();

            bw.close();

        } catch (NumberFormatException e) {

            e.printStackTrace();

        } catch (IOException e) {

            e.printStackTrace();

        }

    }

    

    private static int calc(int m, int n, int x, int y) {

//      x를 고정하고 x에 해당하는 y값을 찾기 위해 m을 계속 더해 해를 찾습니다.

//      x = 5 -> 10을 더하면 해는 15이지만 x는 5입니다.

y값은 10만큼 증가하고 n으로 나머지를 구해주면 y 값이 됩니다.

//      수식으로는 "해 = x + m", y= (x + m) % n

        

//      m = 10, n = 12, x = 3, y = 9를 찾을 경우

//      x에 해를 맞추기 위해 해가 3일 때 x = 3, y = 3입니다.

//      해 = 3 + m -> 13 = 3 + 10이고 y는 (x + m) %n -> (3 + 10) % 12 = 1입니다.

        

//      해가 구해지지 않는 경우는 y를 못찾고 x는 m까지, y는 n까지입니다.

//      m*n로 하면 O(m*n)으로 시간 초과가 나오는 이유입니다. -> m이 1이고 n이 39999

//      y는 n을 벗어나지 않는 다는 전제로 n을 0부터 11까지 반복했을 때

값이 나오지 않는다면 -1를 반환하면 됩니다.

        

        int setY = x; // y 값 임시 저장

        int result = x; // 해

        

        for(int i = 0; i < n; i++) {

//          y는 n의 범위 안에 있으므로 n까지 반복

            

            setY = setY%n;

            if(setY == 0) {

                setY = n;

            }

            if(setY == y) {

                return result;

            }

            result += m;

            setY+=m;

        }

        

        return -1;

    }

    

    

    /*

    private static int calc(int m, int n, int x, int y) {

        int setY = (x % n);

        boolean check = true;

        

        int lcm = lcm(m,n);

        

        int count = 0;

        while (check) {

            if(lcm < count ) {

                check = false;

                return -1;

            }

            x += m;

            setY = ((setY) + m) % n;

            if (y == setY) {

                check = false;

                return x;

            }

            if (setY == n) {

                setY = 0;

            }

            count++;

        }

        return x;

    }

*/

    

    /*

     * Test case 1 : 시간 초과 mCount가 m이 될 때까지, nCount가 n이 될때까지 1씩 증분하여 count를 구합니다.

     * private static int calc(int m, int n, int x, int y) { int mCount = 1; int

     * nCount = 1; int count = 1; boolean check = true; if(x ==1 && y ==1) { return

     * 1; } while(check) { mCount++; nCount++; count++; if(mCount > m) { mCount = 1;

     * } if(nCount > n) { nCount = 1; } if(mCount == 1 && nCount ==1) { check =

     * false; return -1; } if(mCount == x && nCount == y) { check = false; return

     * count; }

     *

     * } return -1; }

     */

    /* Test case2 : 시간 초과 m-n의 값만큼 증분합니다.

     * private static int calc(int m, int n, int x, int y) { // 1. m과 n을 뺍니다.

     * (m-n=k) // 2. k가 양수이면 m > n이고 n이 기준입니다. // k가 음수이면 m < n이고 m이 기준입니다. // 3. k가

     * 양수 일때, x가 k만큼 y로 가는 횟수를 셉니다.(x->y = count) // k가 음수 일때, y가 k만큼 x로 가는 횟수를

     * 셉니다.(y->x = count += 1) // 4. k가 양수 일때, count * n + y가 구하는 해가 됩니다. // k가 음수

     * 일때, count * m + x가 구하는 해가 됩니다.

     *

     * int k = m-n;

     *

     *

     * int count = 0; int result = 0; if(k > 0) { count = checkY(n,k,x,y); if(count

     * == -1) { return count; } result = count *n + y; }else if(k < 0) { count =

     * checkX(m,k,x,y); if(count == -1) { return count; } result = count *m + x;

     * }else {

     *

     * }

     *

     * return result; }

     *

     * // 양수 일 때 private static int checkY(int n, int k, int x, int y) { int count =

     * 0; while(y != x) { x+=k; if((x < 0) || (x > n)) { x = Math.abs(k); } count++;

     * if((x*y) < count) { return -1; } }

     *

     * return ++count; }

     *

     * // 음수 일 때 private static int checkX(int m, int k, int x, int y) { int count =

     * 0; while(x != y) { y+=k; if((y < 0) || (y > m)) { y = Math.abs(k); } count++;

     * if((x*y) < count) { return -1; } }

     *

     * return count; }

     */

    

    /* Test case3 아래 공식을 대입합니다.

     * private static int calc(int m, int n, int x, int y) { // answer = Ma + x = Nb

     * + y

     *

     * int num = 0;

     *

     * boolean check = true;

     *

     * int gcd = gcd(m, n); int lcm = lcm(m,n,gcd); int count = 0; while(check) {

     * num = (m*count) + x; if((num % n) == y) { check = false; } if(lcm < count) {

     * return -1; } count++;

     *

     * } return num; }

     *

     *

     * private static int gcd(int num1, int num2) { int r = num1%num2; if(r != 0) {

     * return gcd(num2, r); }

     *

     * return num2; }

     *

     * private static int lcm(int num1, int num2, int gcd) { return gcd *(num1/gcd)

     * * (num2/gcd); }

     *

     */

}

내 풀이 해석

시간 초과를 해결하기 위해 다른 분들의 풀이를 참고 했습니다.

x과 y가 처음에는 같은 값으로 나가다가 m과 n의 범위를 만나면 초기화됩니다.

다시 m만큼 증가하면 x는 같은 값이 됩니다. 

예를 들어 x가 3이고 m이 10일 때 x에 10을 더해 한바퀴를 돌면 해는 13이 되지만 x는 3이 됩니다.

y는 계속해서 값이 변하고 있습니다.

x를 고정해서 m을 계속 더해 해를 구합니다.

y는 m을 더한 값을 n으로 나누면 y의 값이 됩니다.

x와 y의 값이 찾고자 하는 해가 된다면 출력합니다.

아쉬운 점

20181224

시간 초과. 

식을 다시 찬찬히 살펴봐야겠습니다.

20181226

오래 걸려서풀었습니다.

다른 분들의 풀이를 보고 규칙을 찾았습니다.

손으로 풀다가 처음으로 엑셀을 사용했고 편리했습니다.

기타 참고

참고1

참고2