[파이썬(Python)] 백준 1476번 날짜 계산

 

 

문제

문제 바로 가기

---

📌 문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

 

준규가 사는 나라에서는 연도를 세 가지 값 $E, S, M$으로 나타냅니다. 각각의 값은 특정 주기를 가지며 범위는 아래와 같습니다.

• $1 \leq E \leq 15$
• $1 \leq S \leq 28$
• $1 \leq M \leq 19$

 

 

 

우리가 알고 있는 1년은 준규의 나라에서 $E = 1, S = 1, M = 1$로 나타납니다. 1년이 지날 때마다 $E, S, M$은 각각 1씩 증가하지만 값이 최대 범위를 초과하면 다시 1로 돌아갑니다. 

• $E = 15$인 해의 다음 해는 $E = 1$이 됩니다.
• $S = 28$인 해의 다음 해는 $S = 1$이 됩니다.
• $M = 19$인 해의 다음 해는 $M = 1$이 됩니다. 

 

 

 

이와 같이 반복되는 주기를 가진 $E, S, M$ 값이 주어졌을 때, 해당 연도를 구하는 것이 문제의 목표입니다.

• 입력으로 주어진 $E, S, M$은 항상 유효한 범위 내에 있으며, 조건을 만족하는 연도는 반드시 존재합니다.
• 특히 $E, S, M = 1, 1, 1$일 때는 우리가 알고 있는 1년과 동일하므로 구하고자 하는 연도는 항상 1 이상임이 보장됩니다.

 

 

 

 

 

 

 

아이디어

 

 

1. 첫 번째 방법: 완전 탐색

 

 

가장 간단한 방법은 단순히 1년씩 증가시키면서 조건을 확인하는 방식입니다. 

 

 

1. $\text{year}$를 1부터 시작합니다.

 

2. 각 $\text{year}$에 대해 다음 세 가지 조건을 확인합니다.

• $(\text{year} - E) \% 15 == 0$
• $(\text{year} - S) \% 28 == 0$
• $(\text{year} - M) \% 19 == 0$

 

3. 모든 조건을 만족하면 $\text{year}$를 반환합니다. 

 

 

 

이 방법은 조건을 만족하는 $\text{year}$를 찾기 위해 1년씩 증가하며 모든 경우를 탐색합니다.

 

$E, S, M$의 주기가 각각  $15, 28, 19$이므로 최악의 경우 최소공배수인 7980까지 탐색해야 할 수 있습니다. $E, S, M$ 값이 커질수록 연산량이 급격히 증가하여 시간 초과가 발생할 가능성이 높습니다. 

 

 

 

 

 

 

 

2. 두 번째 방법: 주기별 탐색 범위 축소

 

완전 탐색의 비효율성을 개선하기 위해 특정 조건을 먼저 만족하도록 고정한 뒤 나머지 조건을 확인하는 방법을 사용할 수 있습니다. 이는 문제에서 주어진 주기성을 활용해 탐색 범위를 줄이는 아이디어에 기반합니다. 

 

 

1. $E$ 조건 고정

• $\text{year}$를 $E$부터 시작합니다. 이는 $(\text{year} -E) % 15 == 0$을 항상 만족하도록 합니다.
• $E$ 조건이 자동으로 만족되므로 이후 탐색 범위는 15의 배수 간격으로 줄어듭니다.
• 즉, $\text{year} = E, E+15, E+30, \dots$ 형태로 증가하며 탐색합니다.

 

 

2. $S$와 $M$ 조건 확인

• 각 $\text{year}$에 대해 나머지 두 조건을 확인합니다.
  • $(\text{year} - S) \% 28 == 0$
  • $(\text{year} - M) \% 19 == 0$
• 두 조건을 모두 만족하면 해당 $\text{year}$를 반환합니다.

 

 

$\text{year}$를 1씩 증가시키는 대신 15씩 증가시키므로 $E$ 조건을 항상 만족하게 됩니다. 이후 남은 조건인 $S$와 $M$만 확인하면 되므로 탐색 범위가 크게 줄어듭니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def find_year(e, s, m):
    e -= 1
    s -= 1
    m -= 1

    year = e
    while True:
        if (year % 28 == s) and (year % 19 == m):
            return year + 1
        year += 15 


e, s, m = map(int, input().split())
print(find_year(e, s, m))