백준 문제 중 2225번, 브루트포스, ‘카잉달력’

백준 문제 중 6064번

https://www.acmicpc.net/problem/6064

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

출력

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

---

풀이

Try1

브루트 포스인만큼 단순하게 문제 그대로 접근해 코드를 짰다.

종료조건은 m, n의 최소 공배수보다 클때로 설정했다.

import math

def cal_years(m:int, n:int, x:int, y:int)->int:

    a, b,cnt = 1, 1, 1
    while a!=x or b!=y:
        a, b = a+1 if a+1<=m else 1, b+1 if b+1<=n else 1
        cnt += 1
        if cnt>m*n//math.gcd(m,n):
            cnt = -1
            break
    print(cnt)
t = int(input())
for _ in range(t):
    m,n,x,y = map(int, input().split())
    cal_years(m,n,x,y)

3
10 12 3 9
33
10 12 7 2
-1
13 11 5 5
5

이 문제는 단순하게 접근하면 시간초과가 뜬다. 최적화 할 수 있는 조건을 찾아야지만 시간내에 정답을 찾을 수 있다.

Try2

문제의 해가 가지는 규칙 찾기

m, n, x, y가 10 12 3 9 로 주어진다면 답은 33이다. 그런데 33과 m, n, x, y를 잘 관찰해보자. x는 크기가 m인 링버퍼의 인덱스와 유사하게 수가 증가함을 알 수 있다. 마찬가지로 y는 크기가 n인 링버퍼의 인덱스와 유사하다.

그러므로 구해야될 해를 k라 할때 k%m == x와 k%n == y를 동시에 만족하는 k를 탐색하면 해를 찾을 수 있다. m의 x배수 xm + x 중 k를 찾아도 되고, n의 y배수 yn + y 중 k를 찾아도 된다

여기서 주의해야 할점이 하나 있는데 바로 k%m == x and k%n == y로 조건을 찾는것이 아니고, (k-x)%m == 0 and (k-y)%n == 0으로 조건을 찾는것이다. 얼핏보면 두개의 조건을 같아보이지만 m = 10, n = 12, x = 2, y = 12 일때를 생각해보자. 이를 만족하는 k는 12가 되어야 한다. 여기서 12%2 == 2 를 만족하지만 12%12 == 0이 되어 만족하지 못한다. 즉 k가 바로 m이나 n으로 나누어 떨어질때까지 고려하기 위해 (k-x)%m ==0 and (k-y)%n ==0 를 만족하는 k를 찾으면 된다.

import math

def cal_years(m:int, n:int, x:int, y:int)->int:
    gcd = math.gcd(m,n)
    k = x
    while k<=m*n//gcd:
        if (k-x)%m==0 and (k-y)%n==0:
            return k
        k+=m
    else:
        return -1        


t = int(input())
for _ in range(t):
    m,n,x,y = map(int, input().split())
    print(cal_years(m,n,x,y))

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