6064번: 카잉 달력

문제 출처 : https://www.acmicpc.net/problem/6064

 

언어 : Kotlin

 

문제 설명 :

최근에 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>은 카잉 달력의 마지막 해를 나타낸다.

 

출력 :

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

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
3 10 12 3 9 10 12 7 2 13 11 5 6	33 -1 83

 

풀이 : 

문제 이해에 시간이 조금 걸렸다. <M, N>은 최대치이고, <x, y>는 목표치이다.

예제 1번을 예를 들었을 때, <10, 12>가 최대치이고, <3, 9>가 목표치이다. 출력은 33이므로 33번째에 목표치가 나온다.

 

Index	<x, y>	Index	<x, y>	Index	<x, y>	Index	<x, y>	Index	<x, y>	Index	<x, y>
1	1, 1	7	7, 7	13	3, 1	19	9, 7	25	5, 1	31	1, 7
2	2, 2	8	8, 8	14	4, 2	20	10, 8	26	6, 2	32	2, 8
3	3, 3	9	9, 9	15	5, 3	21	1, 9	27	7, 3	33	3, 9
4	4, 4	10	10, 10	16	6, 4	22	2, 10	28	8, 4
5	5, 5	11	1, 11	17	7, 5	23	3, 11	29	9, 5
6	6, 6	12	2, 12	18	8, 6	24	4, 12	30	10, 6

 

위 표를 기준으로 보면 한번 살펴보자.

목표치는 <3, 9>이고, X를 기준으로 잡아보자.

그럼 X가 3으로 동일할 때, Y의 값이 어떻게 변하는지를 확인해보자.

 

3: <3, 3>

13: <3, 1>

23: <3, 11>

33: <3. 9>

 

X가 3으로 동일할때 Y를 살펴보면 3 -> 1 -> 11 -> 9로 -2씩 일정하게 감소하는 것을 확인할 수 있다.

Y의 최대치는 12이므로 음수가 될때 12를 더해보면 규칙이 완성되는 것을 알 수 있을 것이다.

이렇게 되면 나머지 연산을 통해 답을 구할 수 있다.

 

예를들어, 예제 3번을 보자.

최대치는 <13, 11>이고 목표치는 <5, 6>. 인덱스는 83이라고 한다.

(83 % 13) = 5, (83 % 11) = 6가 나온다.

그러나 나머지값이 0이 나올 경우를 방지하기 위해 x와 y에서 -1을 해준다.

 

x를 기준으로 하므로 반복문을 만들때, idx = x이고, idx += m씩 증가시켜준다.

이때, idx % N이 y와 같다면 위에서 뺀 1을 다시 더하고 해당 값을 도출하면 된다.

 

 

추가적으로 하나 더 해보자.

최대치가 <13, 11>이고, 목표치가 <1, 11>이라고 생각해보자. 인덱스는 모른다.

x를 기준으로 하므로 idx = 1, idx += 13씩 증가한다.

Index	Result
0	0
13	2
26	4
39	6
52	8
65	10

 

처음에 나머지값이 0이 나올 것을 대비해 x, y에 -1을 해줬으므로 <0, 10>이다.

Result가 10으로 y값이 동일하므로 idx + 1을 해주면 결과 인덱스인 66이 구해진다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    repeat(readLine().toInt()) {
        val sb = StringBuilder()
        var (m, n, x, y) = readLine().split(" ").map { it.toInt() }
        x -= 1
        y -= 1

        var idx = x
        while (idx < (n * m)) {
            if (idx % n == y) {
                sb.append("${idx + 1}")
                break
            }
            idx += m
        }

        bw.appendLine(if (sb.isEmpty()) "-1" else sb.toString())
        bw.flush()
    }

    bw.close()
}