[Kotlin, S1] 백준 6064번 카잉 달력

출처: unsplash.com

 

카잉 달력(6064번)

Silver 1

#수학 #브루트포스 알고리즘 #정수론 #중국인의 나머지 정리

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

 

문제 내용

 

 

문제 접근

카잉 제국의 달력 형식은 x : y 형식으로 이루어져 있고 x, y를 정하기 위해 m, n을 사용한다.

위 문제 설명을 해석해 보자면 x < m일 때 x' = x + 1이고 그렇지 않으면 x' = 1이라고 되어 있는데 이는

m = 12일 때 x가 12가 되면 1로 초기화된다는 뜻이다. 이는 x가 1부터 12까지 반복된다는 뜻이다. y도 마찬가지이다.

이 사실을 알았으면 눈치가 빠른 분들은 규칙 파악에 성공했을 것이다. 그럼 바로 코드를 작성하러 가시면 된다.

 

예를 들어 m = 10이고, n = 12일 때 마지막 해는 60이다.

m이 10이면 x는 1부터 12를 반복해서 돌게 되고 y도 1부터 10까지 돌게 된다.

해가 지남에 따라 x와 y가 증가하는데 m 또는 n에 도달하면 1로 돌아가는 구조를 띄고 있다. 이를 이용해 m과 n의 마지막 해를 구할 수 있다. 바로 최소공배수이다.

m이 10이고, n이 12일 때 10과 12의 최소공배수는 60이다. 그리고 60까지 x, y를 계산해 가면서 가다 보면 60일 때 딱 x, y가 각각 10, 12가 될 것이다.

 

그럼 x와 y를 편하게 구할 방법은 있을까? 있다.

바로 나머지를 이용해 x와 y를 구할 수 있다.

m = 10이고, n = 12일 때, 14년째라고 가정하면, 36을 m으로 나눈 나머지는 14 % 10 = 4이고, n으로 나눈 나머지는 14 % 12 = 2라서 달력은 4, 2가 된다.

내가 20년까지 정의한 x, y를 보고 참고해 보자.

사진 1-1

표를 보면 확실히 규칙을 이해할 수 있을 것이다. 각 해에서 m을 나눈 나머지가 x이고, n을 나눈 나머지가 y가 된다.

 

그러면 문제로 돌아가서 m, n, x, y가 주어질 때, x : y가 몇 년인지 구해야 한다.

단순히 1년부터 m, n의 최소공배수까지 반복하면서 나온 년도에서 m과 n을 나눈 나머지가 x, y라면 그 해가 정답이 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()
    val sb = StringBuilder()

    for (i in 0 until case) {
        val (m, n, x, y) = readLine().split(" ").map { it.toInt() }
        val gcd = if (m > n) gcd(m, n) else gcd(n, m)
        val lcm = m * n / gcd

        var year = -1
        for (j in x .. lcm step m) {
            val ry = if (j % n == 0) n else j % n

            if (ry == y) {
                year = j
                break
            }
        }

        sb.append("${year}\n")
    }

    println(sb)
}

private fun gcd(b: Int, s: Int): Int {
    val r = b % s
    return if (r == 0) s
    else gcd(s, r)
}

 

문제 풀이

먼저 m, n의 최소공배수를 구해 준다. 이 값이 반복의 끝이 될 것이다.

반복을 x부터 lcm까지 해주는데 step을 이용해 m을 해주었다. 이렇게 되면 자동으로 나머지가 x인 값만 나오기 때문에 로 나누는 작업을 하지 않아도 되고 시간도 절약할 수 있다.

 

반복 안에서는 x를 이미 만족하는 년도에서 y를 만족하는지 확인하면 된다.

여기서 주의해야 할 사항이 y는 n까지 커질 수 있다. 다르게 말하면 n이 12이면 y도 12까지 커질 수 있다는 뜻이다.

이를 나눈 나머지가 0이 돼버리기 때문에 이를 처리해서 ry로 만들어 준다.

ry가 y랑 같으면 y도 만족하는 값이기 때문에 반복을 빠져나온다.

 

 

문제 해결 과정

반복문 안에 x, y를 동시에 처리하도록 코드를 짜면 최대 반복을 16억 번 돌아야 해서 시간 초과가 발생한다.

그래서 아예 x부터 시작해 step으로 m씩 뛰어넘어 x가 항상 만족하도록 반복 조건을 설정해 주면 시간을 크게 단축시킬 수 있을 것이다.