[백준] 6064번. 카잉 달력(JAVA)

문제

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

---

풀이(32분)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

            sb.append(findYear(m, n, x, y)).append("\n");
        }

        System.out.print(sb);
    }

    public static int findYear(int m, int n, int x, int y) {
        // 0-based index로 변환
        x--;
        y--;

        int lcm = m * n / gcd(m, n); // 최소공배수
        for (int year = x; year < lcm; year += m) {
            if (year % n == y) {
                return year + 1; // 1-based year
            }
        }

        return -1; // 조건을 만족하는 year가 없는 경우
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

 

먼저 해당 풀이를 설명하자면

멸망 연도를 구하여 범위를 설정하기 위해 gcd(최대공약수)를 구한 뒤 이를 이용해 lcm(최소공배수)를 구한다. 이는 도구정리(https://to-travel-coding.tistory.com/82)에 있으니 참고하면 된다.

 

멸망 년도를 구한 뒤에는 브루트포스 방법을 사용하여 모든 경우에 수에 대해 탐색해 나가며 정답을 출력하면 되는 것이다. 이때 알아가면 좋을 부분은 for문에 대한 시작, 조건, 연산에 대해 자유로운 설정을 하는 방법이다. 매번 for(int i = 0; i < n; i++)만 사용하여 for문에 대한 연산이 어색한 부분이 있는데 이 것을 연습해야 될 것 같다.

 

무엇보다 중요한 것은 시간 복잡도와 메모리 사용에 대한 계산이다. 초기 List에 하나씩 넣어두고 이를 .contains연산으로 비교하려고 하였으나 시간 초과가 떴다. 불필요한 연산을 수행하고, 저장하다 보니 생긴 문제이다. 두 번째로 boolean [lcm+1]을 만들어 사용하려고 했지만 이는 메모리초과가 발생했다. 이러한 부분에 대한 고려도 꼼꼼히 하여 문제를 해결하는 연습을 해야 할 것 같다.