[백준] (Swift) 6064번 - 카잉달력 (자세한 설명)

🟠 문제

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

6064번: 카잉 달력

 

🟠 첫번째 풀이 - 틀렸습니다

var n = Int(readLine()!)!

for _ in 0..<n {
    let mnxy = readLine()!.split(separator: " ").map{ Int($0)! }
    var year = 1
    let maxYear = 40000

    while true {
        if (year - mnxy[2]) % mnxy[0] == 0, (year - mnxy[3]) % mnxy[1] == 0 {
            print(year)
            break
        }
        
        if year == maxYear {
            print(-1)
            break
        }
        year += 1
    }
}

첫번재 풀이는 답을 틀렸다. 그냥 내가 maxYear을 40000으로 두고 풀었기 때문이다. 카잉달력에서 만약 M과 N이 10, 12로 주어진다면, 최대 년도는 40000이 아니다. x와 y가 10, 12로 출력되는 60이 최고 년도가 된다. 무슨 공통점이냐면, 주어지는 M과N의 최소공배수가 해당 카잉달력의 최대년도가 되는 것이다. 이것을 전혀 고려하지 않은채 코드를 짜서 문제를 틀렸다.

🟠 두번째 풀이 - 시간초과

최소공배수를 구하는 공식을 추가해주었다.

var n = Int(readLine()!)!

for _ in 0..<n {
    let mnxy = readLine()!.split(separator: " ").map{ Int($0)! }
    var year = 1
    let gcd = mnxy[0] > mnxy[1] ? gcd(mnxy[0], mnxy[1]) : gcd(mnxy[1], mnxy[0])
    let maxYear = (mnxy[0] * mnxy[1]) / gcd

    while true {
        if (year - mnxy[2]) % mnxy[0] == 0, (year - mnxy[3]) % mnxy[1] == 0 {
            print(year)
            break
        }
        if year == maxYear {
            print(-1)
            break
        }
        year += 1
    }
}

private func gcd(_ n: Int, _ m: Int) -> Int {
    return m == 0 ? n : gcd(m, n%m)
}

gcd 메서드를 만들어서 최대공약수를 먼저 구해준다음, 두 수의 곱을 최대공약수로 나눠준 것이 최소공배수가 되는 성질을 이용해서 maxYear을 구했다. 

이렇게 푸니까, 시간초과가 났다. 어쨌든 나의 코드는 year에 +1 해주면서, 작성되는 모든 수에 대하여 가장 최대로 for문을 돌리게 된다. 이부분에서 시간복잡도를 줄여야한다고 생각했다.

maxYear을 전부 살펴보는 방법 대신, 경우의수를 줄여서 보는 방식으로 풀어야한다....

🟠 세번째 풀이 - 맞았습니다!

🔖 M과 N을 구별해서 생각해보자.

내가 처음 풀이한 것은, M과 N을 모두 동시에 고려하면서 year에 +1씩해주었다. 여기서 M과 N을 분리해서 단계별로 생각해보자.

💬 (예제입력1) M = 10, N = 12 

그림처럼 이렇게 10개, 12개씩 반복된다. 결국 우리의 카잉달력은 최대 60개의 값을 가진다. 그렇다면, 형광팬 칠한 부분에서 빨간덩어리는 6덩어리 (60 / 10), 연두색 형광팬 덩어리는 5덩어리 (60 / 12)가 나올 것이다. 

💬 그럼 X = 3 인 경우는 몇가지임?

먼저 X가 3인 경우만 살펴보자. 위에서 빨간덩어리는 6개가 나온다고 했다. 즉, X가 3인 경우도 5가지이다.

X = 3 인 경우 -> ( maxYear / M) 개

 

💬 그렇다면 결국, X=3이면서, Y=9인 경우를 찾으면 되는거 아님?

X = 3일 때는, 몇년일까?

3년, 13년, 23년,,, 이렇게 갈 것이다. 이것을 for문으로 만들어서 규칙을 찾아주면 아래처럼 될 것이다.

for i in 0..<maxYear/M {
	let year = i * M + X
}

year은 각각 3, 13, 23, 33, 43, 53 이렇게 여섯개가 나오겠지!?

그럼 각각 3, 13, 23,,,,일때 y = 9 인 경우를 찾아주자

year가 만약 3이라면, y는 3이된다.
year가 만약 13이라면, y는 1이 된다. y는 N만큼씩 순회하기 때문에 12로 나눠준 나머지값을 갖는다

이것을 코드로 작성해보자.

for i in 0..<maxYear/M {
	let year = i * M + X
    let y = year % N
}

근데 이렇게 하면, 예외사항이 생긴다. 나머지가 0인경우 y는 0이된다. 사실 우리는 0이 아니라 N그대로를 출력해주어야한다. 그래서 아래처럼 삼항연산자를 사용해서 나머지가 0인경우를 처리해주었다.

for i in 0..<maxYear/M {
	let year = i * M + X
    let y = year % N == 0 ? N : year % N
}

이렇게 y까지 판단해주고, 이 y가 입력받은 Y(9)와 같다면, break 해서 for문을 탈출해주자.

 

전체 코드를 보면 아래와 같다. 
이전에는 무조건 40000번을 돌았던것과 달리, 최소의 경우의수 만큼만 for문을 돌게 된다.

var n = Int(readLine()!)!

for _ in 0..<n {
    let mnxy = readLine()!.split(separator: " ").map{ Int($0)! }
    let gcd = mnxy[0] > mnxy[1] ? gcd(mnxy[0], mnxy[1]) : gcd(mnxy[1], mnxy[0])
    let maxYear = (mnxy[0] * mnxy[1]) / gcd
    var isinCal = false

    for i in 0..<maxYear / mnxy[0] {
        let year = i * mnxy[0] + mnxy[2]
        let y = year % mnxy[1] == 0 ? mnxy[1] : year % mnxy[1]

        if y == mnxy[3] {
            print(year)
            isinCal = true
            break
        }
    }

    if !isinCal {
        print(-1)
    }
}

private func gcd(_ n: Int, _ m: Int) -> Int {
    return m == 0 ? n : gcd(m, n%m)
}