[백준] 2217번 로프 [Swift]

문제 링크

2217번: 로프

문제

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

 

문제 풀이

우선 주어진 예제를 이해하며 문제를 이해해보자.

주어진 로프는 10, 15만큼의 중량을 버틸 수 있는 로프이고 각각을 개별로 사용하면 15의 중량을 버틸 수 있지만 병렬로 연결하면 각각의 로프에 모두 고르게 10의 중량을 버틸 수 있으므로 20의 중량을 버틸 수 있게 되어 출력은 20이 나온다.

 

여기서 알 수 있는 것은 병렬로 연결 할 때 버틸 수 있는 질량과 하나의 로프로 버틸 수 있는 질량의 값을 비교해야하며

병렬로 연결할 때 가장 중요한 값은 버틸 수 있는 중량의 값이 가장 작은 값이란 점이다.

 

버틸수 있는 중량의 값이 가장 작은 값에 로프 수를 곱하면 병렬로 버틸 수 있는 최대 중량의 값이 나온다.

 

하지만 문제에 주어진 조건에 모든 로프를 반드시 사용해야할 필요는 없기 때문에 다음과 같은 예외가 나올 수 있다.

예를 들어 3개의 로프가 주어지고 각각 10, 100, 110의 무게를 버틸수 있다고 하자.

그렇게 되면 10을 버티는 로프를 사용하지 않고 100, 110의 무게를 버티는 로프만 사용하는게 더 효과적이다.

 

따라서 로프가 버틸 수 있는 질량을 오름차순으로 정렬하고 로프를 몇 개를 병렬로 연결하는 것이 더 효과적인지를 계산해줘야한다.

이렇게 나온 값의 최대값과 하나의 로프만 사용했을 때의 최대값을 비교하여 정답을 구할 수 있다.

소스 코드

func solution() -> Int {
    let n = Int(readLine()!)!
    var ropes = [Int]()
    
    for _ in 0..<n{
        ropes.append(Int(readLine()!)!)
    }
    
    ropes = ropes.sorted()
    let strongestRope = ropes[n-1]
    var result = 0
    
    for (index,weakestRope) in ropes.enumerated(){
        if (weakestRope * (n-index)) > result {
            result = (weakestRope * (n - index))
        }
    }
    
    if result > strongestRope{
        return result
    }

    return strongestRope
}

print(solution())