[swift][백준 알고리즘] 6064 카잉 달력

문제:    

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

6064번: 카잉 달력

풀이방법:    

M	N	x	y
10	12	3	9

문제를 식으로 정리하면

M, x : ( k-x ) % M = 0

N, y : ( k-y ) % N= 0

를 만족하는 k의 값을 구하는 문제이다.

 

( k-x ) % M = 0을 만족하는 첫번째 식인 

k = x일 때부터 k = x + M , k = x + 2M, ...이렇게 k에 M을 증가시키며 계산을 한다. 

그리고 만약 이 k가 ( k-y ) % N == 0 식을 만족한다면 k를 반환한다.

 

마지막으로 k가 x와 y의 최소공배수를 초과할 시에는 -1 반환한다.

(최소공배수이기 전의 과정이 반복됨)

 

작성한 코드는 다음과 같다.

import Foundation

// 반복 횟수 T
let T = Int(readLine()!)!

// 최대 공약수 (최소공배수를 구하기 위해)
func GCD(_ A : Int,_ B : Int)->Int{
    if(A % B == 0){
        return B
    }else{
        return GCD(B,A%B)
    }
}

// 최소공배수
func LCM(_ A : Int,_ B : Int)->Int{
    return A * B / GCD(A, B)
}

// k 값 구하는 함수
func result( _ N : Int, _ M : Int, _ x: Int, _ y : Int)->Int{
    var k = x
    // k가 M과 N의 최소공배수 이하일 때까지 반복
    while(k <= LCM(M,N)){
    	// k가 "(k-y) % N == 0" 조건에 해당하면 k 반환
        if((k-y)%N == 0){
            return k
        }
        // k는 처음 x 값에서 M을 더해나감
        k += M
    }
    // k가 M과 N의 최소공배수를 넘어섰을 때 -1 반환
    return -1
}

for _ in 0..<T {
    let inputArray = readLine()!.split(separator: " ")
    let M : Int = Int(inputArray[0])!
    let N : Int = Int(inputArray[1])!
    let x : Int = Int(inputArray[2])!
    let y : Int = Int(inputArray[3])!
   print(result(N,M,x,y))
}

 

성공한 사진!