[백준, 1476번] 날짜 계산 (브루트 포스 , Java)

 

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 날짜 계산" 문제는 (E, S, M)이 각각 주어진 값으로 표현되는 연도를 구하는 것이 문제입니다.

 

연도를 1부터 시작하여, 주어진 E,S,M과 같은 값이 되는 연도를 찾습니다.

 

이번 문제의 핵심은 위와 같이 브루트 포스 알고리즘을 사용하여 1부터 시작하여 주어진 E,S,M과 같은 연도를 찾는 것 입니다.

 

[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기

지구, 태양, 달의 주기

• 지구(E)는 1년부터 15년까지 반복됩니다. → 즉, y%15=E (지구의 연도)
• 태양(S)은 1년부터 28년까지 반복됩니다. → 즉, y%28=S (태양의 연도)
• 달(M)은 1년부터 19년까지 반복됩니다. → 즉, y%19=M (달의 연도)

또한 위와 같이 지구, 태양, 달은 범위에 따라 반복됩니다. 따라서 저는 각 달력의 연도가 고유한 주기를 가지며, 범위를 벗어나면 순환적으로 반복되기 때문에 나머지 연산을 사용했습니다.

[TIL, 일일 회고] 2024.09.24 - 나머지 연산(%)을 활용한 배열 순환 처리 방법

전체 코드

 

1. 입력 처리 

• BufferedReader와 StringTokenizer를 사용하여 한 줄로 주어진 세 정수를 입력받습니다.
  • E: 지구를 기준으로 한 값 (1 ≤ E ≤ 15)
  • S: 태양을 기준으로 한 값 (1 ≤ S ≤ 28)
  • M: 달을 기준으로 한 값 (1 ≤ M ≤ 19)

2. 초기값 설정

• 연도(year)를 1부터 시작합니다.

3. 반복문으로 조건 확인

 

• 한 반복문(while (true))을 통해 조건을 만족할 때까지 year를 1씩 증가시킵니다.
• 각 연도의 E, S, M 값을 계산:
  • e: year % 15이 0이면 15, 아니면 나머지 값
  • s: year % 28이 0이면 28, 아니면 나머지 값
  • m: year % 19이 0이면 19, 아니면 나머지 값
• 주어진 값 E, S, M과 계산된 e, s, m이 모두 일치하면, 현재 연도(year)를 출력하고 반복문을 종료합니다.
• 그렇지 않다면 연도를 1 증가시킵니다.

 

---

여기서 주의해야할 점은 아래와 같이 코드를 작성하면 시간 초과가 발생합니다.

public class BOJ1476 {
    public static void main(String[] args) throws IOException {
    // 코드 생략
    
        while (true){
            if(year % 15 == E && year % 28 == S && year % 19 == M){
                break;
            }
            year++;
        }
    }
}

 

위 코드의 문제점은 다음과 같습니다.

• E가 15일 때: year % 15는 0이 됨, 하지만 0 == 15는 false
• S가 28일 때: year % 28는 0이 됨, 하지만 0 == 28는 false
• M이 19일 때: year % 19는 0이 됨, 하지만 0 == 19는 false

즉, 나머지가 0일 때 각각의 최대값(15, 28, 19)으로 변환해주지 않아 무한루프에 잠기게 됩니다.