[Swift][Bruteforce] 백준 6064번(카잉 달력)

요구능력

효율적인 브루트포스, 유클리드호제법

 

문제풀이

처음에는 무작정 돌리다가 시간초과가 났는데, 그 이유는 시간복잡도가 O(N * M)이 되서 최악의 경우에는 40000 * 40000번이 돌아갔기 때문이다..

 

그럼 시간을 줄이는 방법은 뭐가 있을까?

이렇게 x와 y와 같이 두 개의 수를 사용해서 목표값을 맞추는 문제는 하나의 값을 고정하고 문제를 풀면 시간이 꽤 많이 단축된다.

x값을 고정해서 문제를 풀어보자.

curX, curY를 각각 목표값 x,y에 맞추기 위한 수 라고 생각해보자.

예제의 첫번째인 10, 12, 3, 9로 예를 들어보면,

그럼 curX는 3으로 고정이다.

우리는 curY값이 9가될 때 몇 번째 해인지 출력해주면 된다.

단순히 1씩 더해서 9가되는건 당연히 아니다.

처음에 curY값은 x와 같을 것이다.

이유는 카잉달력은 x:y가 1,1부터 시작해서 2,2 ... 와 같이 x,y가 같이 1씩 더해지기 때문에, y의 맨 처음의 경우의 수는 x와 같은 수가 들어가야한다.

하지만, 여기서 N이 x보다 작은경우도 고려를 해줘야한다.

이유는 y도 마찬가지로 y가 N보다 작을경우 y + 1 이지만, n과 같을경우 y = 1이 되기 때문이다.

그래서 처음 curY = (x - 1) % n + 1 이된다.

그냥 x % n 하면 되지 않나요?

그냥 x % n을 해버리면, x 와 n이 같을 경우에 1이 아닌 0이 나오게되고 x % n + 1 만 해버리면 5 % 13 과 같은 경우에 5가 나와야하는데 6이나와버린다. 이런경우를 고려해서 미리 1을 빼준다.

 

그리고 이 문제는 <x:y>가 유효하지 않은 표현이면 -1을 출력하라고 한다.

이걸 어떻게하지 하다가 찾아봤는데, <10:12>는 마지막해인 60번째 해를 나타낸다가 이 문제의 힌트라고한다.

10과 12의 최소공배수가 60이니까...

결론은 최소공배수가 마지막해라는 것이다.

최소공배수는 유클리드호제법을 이용해서 구해주면 쉽다.

 

이 문제는 결국, 마지막해(최소공배수)까지만 돌면서 curY를 m씩 더해주면서 y값과 맞는지를 확인하면된다.

m씩더해주는 이유는 x값을 고정시켜놨고 x값을 고정시켜놨다는건 curY값을 x값이 변하는 주기(M) 만큼씩 변화시켜줘야한다.

이렇게해서 둘이 같아져야 문제에서 요구하는 x, y를 맞추는것이기 때문이다.

후기

알고리즘 자체는 쉬운데, 생각해내는게 어려운 문제

 

코드

var t = Int(String(readLine()!))!
for _ in 0..<t {
    let mnxy = readLine()!.split(separator: " ").map{Int(String($0))!}
    let m = mnxy[0]
    let n = mnxy[1]
    let x = mnxy[2]
    let y = mnxy[3]

    var curY = (x - 1) % n + 1
    var count = x
    let least = lcm(m, n)
    var result = -1
    
    while count < least{
        if curY == y{
            result = count
            break
        }
        curY = (curY + m - 1) % n + 1
        count += m
    }
    print(result)
}
func gcd(a: Int, b: Int) -> Int{
    var curA = a
    var curB = b
    while curB != 0{
        let r = curA % curB
        curA = curB
        curB = r
    }
    return curA
}
func lcm(_ a: Int,_ b: Int) -> Int{
    return a * b / gcd(a: a, b: b)
}