[백준][6064번] 카잉 달력

문제 URL

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

시간초과 풀이

import java.io.*;
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 size = Integer.parseInt(br.readLine());
        int[][] arr = new int[size][4];

        for (int i = 0; i < size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < size; i++) {
            for (int j = 0; ; j++) {
                int m = j % arr[i][0];
                int n = j % arr[i][1];
                if (m == (arr[i][2] - 1) && n == (arr[i][3] - 1)) {
                    bw.write((j + 1) + "\n");
                    break;
                } else if (m == (arr[i][0] - 1) && n == (arr[i][1] - 1)) {
                    bw.write(-1 + "\n");
                    break;
                }
            }
        }

        bw.flush();
        bw.close();
    }
}

해결한 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[][] arr = new int[size][4];

        for (int i = 0; i < size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < size; i++) {
            boolean flag = true;
            for (int j = arr[i][2] - 1;j<arr[i][0]*arr[i][1]; j+=arr[i][0]) {
                int m = j % arr[i][0];
                int n = j % arr[i][1];
                if(m == arr[i][2]-1 && n == arr[i][3] -1) {
                    System.out.println((j + 1));
                    flag = false;
                    break;
                }
            }
            if(flag)
                System.out.println(-1);
        }
    }
}

다른 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(bf.readLine());
        while (t-- > 0) {
            String[] line = bf.readLine().split(" ");
            int m = Integer.valueOf(line[0]);
            int n = Integer.valueOf(line[1]);
            int x = Integer.valueOf(line[2])-1;
            int y = Integer.valueOf(line[3])-1;
            boolean ok = false;
            for (int k=x; k<(n*m); k+=m) {
                if (k%n == y) {
                    System.out.println(k+1);
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                System.out.println(-1);
            }
        }
    }
}

느낀점

브루트 포스를 계산하기전 경우의수를 먼저 계산해서 생각해낸 풀이법이 적절한지 먼저 판단해야겠다.

• 시간초과 이유 앞서 푼 날짜계산문제와 비슷했다. (이 문제와 차이를 보고오자) (https://www.acmicpc.net/problem/1476)

하지만 1476번 문제는 경우의수가 적었다.(총 8천가지) 이 문제 같은경우는 M,N <= 40000 이므로 경우의수는 총 16억가지 로 다른 풀이를 생각해야한다.

• 다른풀이

1. 위 그림과 같이 앞수는 m을 주기로 반복, 뒷수는 n을 주기로 반복한다. 즉, x를 이용해 모든 해를 고려하지 않고, i×M+x (i ≥ 0)의 형태만 조사하면 된다 (최대 N번 탐색) -> 시간복잡도 : O(N)

2. 1476번 문제와 같이 -1을 먼저 하고 계산하면 m,n을 나눈 나머지로 그대로 계산가능하다.