알고리즘 풀이 - 백준 6064(카잉 달력, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

 

 

2. 풀이

 

이전의 날짜 계산 문제(관련 포스팅은 여기)와 매우 유사하지만, 이번엔 m, n 의 최대값이 40,000이다. 즉, 최대 16억의 경우의 수가 있기 때문에 1초 이내에 풀 수가 없다.

따라서 우리는 완전 탐색으로 수행하되 모든 것을 탐색하는 것이 아니라 규칙을 이용해 건너뛰면서 탐색해야 한다.

우선, 나머지 정리를 활용하기 위해 현재 년도를 x, y라고 할 때, 각각을 1씩 제외해주자.(나머지 정리 또한 이전 포스팅 참조)

 

그렇다면, 현재 x값으로 시작해서 최대인 m*n까지 탐색을 하되 x는 m 간격으로 건너 뛰고, 그 현재 값을 n으로 나눈 나머지가 y와 같다면 그 때의 년도+1이 정답이 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

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 t = Integer.parseInt(br.readLine());
        for(int i=0; i < t; i++){
            String line[] = br.readLine().split(" ");
            int m = Integer.parseInt(line[0]);
            int n = Integer.parseInt(line[1]);
            
            // -1을 빼고 시작하여 나머지 정리 방식을 사용할 수 있도록 설정
            int x = Integer.parseInt(line[2])-1;
            int y = Integer.parseInt(line[3])-1;
            
            int year = -1;
            for(int j=x; j < m*n; j+=m){
                if(j%n == y){
                    year = j+1;
                    break;
                }
            }
            bw.write(String.valueOf(year) + "\n");
        }
        
        bw.flush();
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.