[백준] (Swift) 2981번: 검문

📌 문제

[백준] (Swift) 2981번: 검문

 

📌 풀이

문제를 푸는데 수학적인 센스가 필요한 문제가 있는데 이 문제가 대표적인 것 같다. 입력 받는 값을 '나머지'의 관점으로 다시 생각해 보자.

 

종이에 적힌 모든 숫자를 적은 배열 papers에서 임의의 숫자 m으로 나누었을 때 나머지가 같은 두 요소를 A, B라 하자. 이를 아래와 같이 표현할 수 있을 것이다.

$papers\begin{cases} A = ma + r \\ B = mb + r \end{cases}$

 

두 요소를 한번 빼 보면 나머지가 없어지는 걸 확인할 수 있다.

$A - B = m(a - b)$

 

아래 2가지가 문제 풀이의 핵심인 것 같다.

1. 이렇게 나머지를 없앤 요소를 하나씩 모아서 최대공약수를 구하고
2. 1번을 제외한 최대공약수의 공약수를 모두 구하는 것

모든 수의 최대공약수를 구하기 위해 인접한 두 요소를 서로 빼기로 했다. 그럼 모든 요소가 서로 겹치기 때문에 최대공약수를 구할 수 있다. 최대공약수를 구했으면 이제 그 수의 약수를 구하면 된다.

 

📌 코드

import Foundation

// 입력값 할당
let N: Int = Int(readLine()!)!

// 필요한 컬렉션 변수 정의
var papers: [Int] = []
var newArr: [Int] = []
var result: Set<Int> = []

// 최대공약수를 구하는 함수 정의
func findGCD(_ a: Int, _ b: Int) -> Int {
    return a % b == 0 ? b : findGCD(b, a % b)
}

// N번을 돌며 종이가 적힌 배열에 주어진 입력 값을 할당
for _ in 1...N {
    papers.append(Int(readLine()!)!)
}

// 종이가 적힌 배열 정렬
papers = papers.sorted()

// 인접한 배열을 서로 빼면서 새 배열 할당
for i in 1..<papers.count {
    newArr.append(papers[i] - papers[i - 1])
}

// 새 배열의 최대공약수를 구함
var GCD: Int = newArr[0]
for i in 1..<newArr.count {
    GCD = findGCD(GCD, newArr[i])
}

// 최대공약수의 약수를 result 집합에 추가
for i in 2..<Int(Double(GCD).squareRoot()) + 1 {
    if GCD % i == 0 {
        result.insert(i)
        result.insert(GCD / i)
    }
}
// 최대공약수 또한 result 집합에 추가
result.insert(GCD)

// result를 정렬 후 요소를 공백으로 구분한 문자열로 출력
print(result.sorted().map { String($0) }.joined(separator: " "))