[백준(baekjoon) 6064] (최대공약수/규칙 찾기) 카잉 달력

문제 백준 6064

M, N, X, Y가 주어질 때 가 몇 번째 해인지 구하여라.
단, 답이 존재 하지 않는 다면 -1

• 1 <= M,N <= 40,000이고 첫번째 해가 <1:1>이고 마지막 해가 인 달력이 있다.
• 1 <= x <= M, 1 <= y <= N인 수로 년도를 로 표현함.
• <x, y>의 다음 해를 <x':y'>라고 할 때
  x' = x + 1이지만, x' > m이면 x' = 1 (y 역시 n에 대하여 동일)

해결

1. 정답이 존재할 경우, 정답은 다음과 같이 나타낼 수 있다.

자연수 a, b가 있을 때
answer = Ma + x = Nb + y

즉, x와 y는 정답에서 M, N을 나눈 나머지 가 됨을 알 수 있다.
(단 M = x, N = y일 경우 0이 되므로 이 경우를 고려한다.)

• x = 정답 % a
• y = 정답 % b

2. answer = Ma + x = Nb + y 을 활용해 정답을 구할 수 있을 것 같다.

• M, x를 알고있으므로 a를 1부터 1씩 증가시켜서 num = Ma + x를 구한다.
• num이 정답이라면 num % N == y일 것이다.

3. 그리고 여기서 시간을 더 줄여보자.

(이 과정을 거치지 않아도 통과 가능하긴 합니다.)

2번 과정에서 num을 구하기 위해 증가하는 a의 횟수가 실행시간에 중요한 역할을 한다.
그리고 당연히 이 a대신 b를 증가시켜도 된다.
그렇다면 M, N 중 큰 수를 기준으로 삼아 num을 구하면 당연히 실행횟수가 줄어들 것.

1.ex) answer = 39999, M = 39999, N = 1일때 a = 1, b = 39999가 된다.

answer = Ma + x = Nb + y 여기서 M <= N이라면, a >= b 이다.
즉 2번에서 num을 구하는 M역할을 M, N 중 큰 수로 대체한다.

4. 그렇다면 -1이 되는 경우는 언제인가?

마지막 해는 M, N의 [최대공약수]번째에 나타난다.

마지막 해는 x = M, y = N을 만족한다. 1번에 대입하면 x = 0, y = 0이다.
즉, 정답을 M, N으로 나눈 나머지가 0을 만족한다는 것을 뜻한다.

M, N을 나눈 나머지가 0이라는 말은 즉 M, N의 최대공약수를 뜻한다.
즉, 정답은 최대공약수 보다 작다.

이를 활용해 최대공약수를 벗어날 경우 -1이 답 임을 알 수 있다.

최대공약수 구하는 법 보러가기

구현

언어 : swift

1.import Foundation
2.
3.// 최대공약수 구하는 함수
4.func getLcm(l: Int, s: Int) -> Int {
5.    var large = l; var small = s
6.    var rest = large % small
7.    while rest > 0 {
8.        large = small
9.        small = rest
10.        rest = large % small
11.    }
12.    return l * s / small
13.}
14.
15.let count = Int(readLine()!)!
16.// 정답을 우선 -1로 모두 초기화 한다.
17.var answer = Array(repeatElement(-1, count: count))
18.for i in 0..<count {
19.    var input = readLine()!.split(separator: " ").map{ Int($0)! }
20.
21.    // 쉬운 구현을 위해
22.    // m = x, n = y인 경우 0으로 변경해준다.
23.    input[2] = input[2] == input[0] ? 0 : input[2]
24.    input[3] = input[3] == input[1] ? 0 : input[3]
25.
26.    // m, n 중 큰 수와 작은 수의 인덱스를 각각 l, s에 저장한다.
27.    // x, y의 위치는 l, s에 2를 더한 곳이다.
28.    let l = input[0] > input[1] ? 0 : 1; let s = abs(l - 1)
29.    let lcm = getLcm(l: input[l], s: input[s])
30.    // num의 큰 수의 나머지 부터 시작하지만
31.    // 나머지가 0인 경우 num은 자연수 이므로 큰 수부터 시작한다.
32.    var num = input[l + 2] > 0 ? input[l + 2] : input[l]
33.
34.    // num이 최대공약수보다 클 수 없다.
35.    while num <= lcm {
36.        if num % input[s] == input[s + 2] {
37.            answer[i] = num
38.            break
39.        }
40.        num += input[l]
41.    }
42.}
43.
44.for a in answer {
45.    print(a)
46.}