백준 Swift [2485] 가로수

난이도

실버 IV

 

문제

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

2485번: 가로수

 

내 답안

var trees = [Int]()

for _ in 1...Int(readLine()!)! {
    trees.append(Int(readLine()!)!)
}

func gcd(bigOne: Int, smallOne: Int) -> Int {
    if smallOne == 0 {
        return bigOne
    }

    return gcd(bigOne: smallOne, smallOne: bigOne % smallOne)
}

var divisor = 0

for i in 0...trees.count - 2 {
    divisor = gcd(bigOne: trees[i + 1] - trees[i], smallOne: divisor)
}

print(((trees.last! - trees.first!) / divisor) + 1 - trees.count)

• 핵심은
  • 최대공약수를 구하고
  • 필요한 나무 수는 전체 길이(마지막 나무 위치 - 처음 나무 위치) / 최대공약수 + 1 이었다.
• 처음에는 for문을 통해 간격을 배열로 담아 큰 값과 작은 값을 사용하여 gcd를 이용하여 divisor를 구했는데 계속 오답이라고 나왔다.
• 결과적으로 매 간격마다 gcd를 사용하는 것으로 해결은 되었지만 왜 그런건지 이해가 되지 않았다.
  •  아마 각 간격을 배열에 담은 것을 max와 min을 사용하지 않고 각각 구했으면 통과가 되었을텐데 max와 min을 사용한 한 케이스만 적용했기 때문에 반례가 있었던 것 같다.
  • 또 하나 이해되지 않은 점은, 유클리드 호제법에서는 m이 n보다 큰 값이라는 조건이 있었는데 배열에 있는 값 혹은 각 간격을 gcd 돌리게 되면 그 조건이 맞지 않는 경우도 생기지 않나 하는 것이었다.
    하지만 gcd 가설을 통해 bigOne에 작은 값이, smallOne에 큰 값이 들어온 경우를 상정해본 결과 어쨌든 그 순서로 가게 되어있더라..