[백준] 6064. 카잉 달력

 

📪 [카잉 달력]

 

6064번: 카잉 달력

 

---

 

 

📋 문제설명

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다.

• 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다.
• 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다.
• <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다.
• 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다.
• <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.
• 예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

 

 

 

 

👁‍🗨 입출력 데이터

[입력]

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다.

입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.

각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)

여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

3
10 12 3 9
10 12 7 2
13 11 5 6

[출력]

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

33
-1
83

 

 

 

 

🔑 문제풀이

문제를 풀면서 작성한 코드들은 다음과 같다. 

 

  ※ [참고] 잘못된 첫 번째 풀이

from sys import stdin


def get_year(max_x, max_y, val_x, val_y) -> int:
    if val_x == val_y == 1:
        return 1
    for i in range(2, max_x * max_y + 1):
        if (max_x - val_x) % i == 0 and (max_y - val_y) % i == 0:
            return i
    return -1


if __name__ == '__main__':
    t = int(stdin.readline().rstrip())
    ans_list = []

    for i in range(t):
        m, n, x, y = map(int, stdin.readline().split())
        ans_list.append(str(get_year(m, n, x, y)))
    ans = '\n'.join(ans_list)
    print(ans)

첫 번째 풀이 코드의 경우 위와 같았다. 이에 주어진 테스트 케이스를 돌려보았더니 결과는 엉망진창이었다.

get_year()이라는 함수 내부의 조건문을 if (max_x - val_x) % i == 0 and (max_y - val_y) % i == 0라고 하였는데, 해당 조건식이 잘못되었기 때문이었다. 즉, 이는 필요충분조건을 만족하는 조건식이 아니기 때문이다.

예를 들어 max_x, max_y가 10, 12이고 val_x, val_y가 4, 4라고 해보자. 이 경우, 정답인 i는 4이어야 한다. 

허나 i=2일 경우, max_x - val_x와 max_y - val_y 모두 2로 나누어 떨어지므로 조건문을 만족해 답으로 인식되게 된다. 즉 즉 i=4일 경우 조건문을 만족하긴 하지만 해당 경우에만 만족하는 것이 아니므로 필요충분한 조건이 아니기에 이는 잘못된 조건문이다. 따라서 필요충분 요건을 만족하도록 조건문을 수정하여 코드를 재작성해주었다. 코드는 아래와 같다.
👉 엥 그냥 다 잘못된 듯? i를 나눠야되는데 i로 나눴네. 해당 풀이 무시하기.

 

from sys import stdin


def get_year(max_x, max_y, val_x, val_y) -> int:
    for i in range(1, max_x * max_y + 1):
        if (i % max_x == val_x % max_x) and (i % max_y == val_y % max_y):    # same as (i-1) % max_x == (val_x - 1)..
            return i
    return -1


if __name__ == '__main__':
    t = int(stdin.readline().rstrip())
    ans_list = []

    for i in range(t):
        m, n, x, y = map(int, stdin.readline().split())
        ans_list.append(str(get_year(m, n, x, y)))
    ans = '\n'.join(ans_list)
    print(ans)

두 번째 풀이 코드의 경우, 첫 번째 코드의 문제를 보완하여 작성하였기에 백준 사이트에서 제공하는 테스트케이스를 만족하였다. 허나 제출시 시간초과 문제가 발생하는 것을 확인할 수 있었다. 이는 M과 N의 범위가 1이상 40,000 이하인데 전체 경우의 수인 M*N이 1,600,000,000가지가 되어버리므로 시간제한인 1초를 넘기기 때문이었다. (1초=1억)

그렇다면 모든 경우의 수를 계산해서는 안된다는 것인데 이를 어떻게 해야할까? 

 

구하고자 하는 수를 □라고 하자. □는 다음과 같은 두 가지 조건을 만족해야 한다.

1. □를 M으로 나눈 나머지 = X (이때, M과 X는 상수)
2. □를 N으로 나눈 나머지 = Y (이때, N과 Y는 상수)

이 중 1을 다르게 표현해보면 '□ = i * M + X'라는 것이다. 또한 이는 2의 조건을 만족해야 하는데, 2의 조건에 해당하는 수는 N을 주기로 반복된다. 즉 구하고자 하는 수 □는 M*N이내의 모든 수에서 찾을 필요 없이, 해당 식에서 i가 0<=i<=N인 범위에서 찾기만 하면 된다. 이를 이용하면 경우의 수가 1<=N<=40,000으로 확연히 줄게 된다. 반영하여 짠 코드는 아래와 같다.

 

from sys import stdin


def get_year(max_x, max_y, val_x, val_y) -> int:
    for k in range(0, max_y):
        if (k * max_x + val_x) % max_y == val_y % max_y:
            return k * max_x + val_x
    return -1


if __name__ == '__main__':
    t = int(stdin.readline().rstrip())
    ans_list = []

    for i in range(t):
        m, n, x, y = map(int, stdin.readline().split())
        ans_list.append(str(get_year(m, n, x, y)))
    ans = '\n'.join(ans_list)
    print(ans)

→ 이때 1<=val_x<=N이므로 %N의 값 주의하기!

 

 

 

 

 

---

 

🔔 풀이/개념정리

1. 브루트포스 문제에서 경우의 수가 너무 多!
   👉 M*N = 16억으로 시간이 초과되기 때문.
   → 모든 경우를 구하는 방법을 배제해보기. 
   → 건너 뛰어 구할 수 있는 경우 고려해보기. 
   → 아하, 둘 중 하나의 범위만 고려해야 겠구나라고 추측! 👌
2. 모듈러(%) TIP
   → X % N = X'이면, (X-X')%N = 0이다.
   
3. ⭐ %N의 값과 결과값의 범위가 다를때 주의하기! ⭐
   → 0<= %N <= N-1인데 1<=결과값<=N인 경우!