알고리즘 풀이 - 백준 1476(날짜 계산, 완전 탐색)

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

지구(E), 태양(S), 달(M)의 3가지 수를 이용해 연도를 나타낼 때, 우리 날짜로는 몇 년도인지 환산하는 문제

 

 

2. 풀이

 

이 문제를 푸는 간단한 방법은 1부터 시작하여 1씩 더해가며 비교하는 방법이다.

주어지는 E, S, M을 미리 저장하고, 다른 변수를 만들어 1씩 더해가면서 E, S, M의 값과 모두 일치해지는 값을 찾은 경우 그 경우의 결과값을 반환하면 정답이 된다.

 

이 문제는 E는 최대 15, S는 28, M은 19이므로 3개의 값을 모두 합하면 7980이 되어 경우의 수가 매우 적어 완전 탐색으로 간단하게 풀 수 있다.

별도의 추가 설명 없이 아래의 코드를 통해 정답을 알아보자.

 

※ 참고 - 중국인의 나머지 정리

현재 년도를 year라는 변수로 저장한다고 가정할 때, 아래의 조건을 만족하는 가장 작은 값이 정답이 된다.

현재 년도 year에서 각 E, S, M의 최대값으로 나누어 각각 E-1, S-1, M-1과 같은 경우 해당 year+1이 정답이다.

●  year MOD 15 == E-1
●  year MOD 28 == S-1
●  year MOD 19 == M-1

왜 -1을 하냐면, 최대값에 다다르면 나머지가 0이되어 정확한 숫자 처리가 안되어 예외 처리를 위해 미리 1을 빼고 나중에 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));
        
        String esm[] = br.readLine().split(" ");
        
        // ESM으로 표시한 년도 값 각각 저장
        int e = Integer.parseInt(esm[0]);
        int s = Integer.parseInt(esm[1]);
        int m = Integer.parseInt(esm[2]);
        
        // 1부터 시작해서 ++ 해나가며 일치 여부 확인
        int ce = 1; int cs = 1; int cm = 1;
        
        
        int i=1;
        for(;i <= 15*28*19; i++,ce++,cs++,cm++){
            // 모두 일치 시 반복문 탈출
            if(e==ce && s==cs && m==cm){
                break;
            }
            
            // 마지막 값인 경우 0으로 초기화
            if(ce == 15) ce = 0;
            if(cs == 28) cs = 0;
            if(cm == 19) cm = 0;
        }
        
        bw.write(String.valueOf(i));
        bw.flush();
        br.close();
    }
}

 

※ 중국인의 나머지 정리 방식

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));
        
        String esm[] = br.readLine().split(" ");
        
        // ESM으로 표시한 년도 값 각각 저장
        int e = Integer.parseInt(esm[0]) - 1;
        int s = Integer.parseInt(esm[1]) - 1;
        int m = Integer.parseInt(esm[2]) - 1;
        
        int i=0;
        for(;; i++){
            // 모두 일치 시 반복문 탈출
            if(i % 15 == e && i % 28 == s && i % 19 == m){
                break;
            }
        }
        
        bw.write(String.valueOf(i+1));
        bw.flush();
        br.close();
    }
}

 

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