streetree

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 각 나무의 위치를 나타내는 정수는 모두 다르고, 가까운 위치(오름차순)로 주어짐
2. 따라서 각 정수의 차에 대한 최대공약수가 같은 간격으로 최소한의 나무를 심을 수 있는 값임을 알 수 있음
3. 가로수의 위치를 나타내는 정수의 최고 크기가 1,000,000,000 이므로, 완전 탐색으로 해당 나무가 심어져 있는지 확인 하기 위해 최악의 경우 O(N)으로(최대공약수가 1인 경우) 문제를 해결할 경우, 시간 내에 해결하지 못할 수 있음
4. 따라서, 주어진 정수 중 최대값과 최소값의 차이를 같은 간격(최대공약수)로 나누게 되면, 최대로 필요한 간격을 구할 수 있고 + 1을 하게 되면 총 나무의 개수를 구할 수 있음.
5. 이미 심어져 있는 나무의 개수는 문제에서 주어졌으므로 위 4번에서 구한 값에서 N(이미 심어져 있는 나무의 개수)을 제외시킴으로써 문제를 해결할 수 있음

5. 전체 코드

//
//  main.swift
//  Streetree
//
//  Created by 이영재 on 2022/03/08.
//MARK: - streetree

//MARK: - Framework
import Foundation

//MARK: - Function
func getGCD(_ A: Int, _ B: Int) -> Int {
    return A % B == 0 ? B : getGCD(B, A % B)
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    var answer: Int = 0
    var difference: Int
    var trees: [Int] = []
    var differences: [Int] = Array(repeating: 0, count: N + 10)
    
    for _ in 0..<N {
        guard let tree: Int = Int(readLine() ?? "0") else { return }
        trees.append(tree)
    }
    
    //MARK: - Process
    for i in 1..<N {
        differences[i - 1] = trees[i] - trees[i - 1]
    }
    
    difference = differences[0]
    for i in 1..<(N - 1) {
        difference = getGCD(difference, differences[i])
    }
    
    answer = (trees[N - 1] - trees[0]) / difference + 1 - N
    
    //MARK: - Output
    print(answer)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.