로프

백준 2217번

문제

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

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

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

 

입력

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

출력

첫째 줄에 답을 출력한다.

 

예제 입력

2
10
15

 

예제 출력

20

 

풀이 과정

1. 반복문을 돌며 선택된 로프들이 견딜 수 있는 최대 무게를 새로운 배열 weights에 담는다.

2. weights에서 최댓값을 출력한다.

ex)
rope = [1, 2, 3, 4]

# loop 1
1
1, 2
1, 2, 3
1, 2, 3, 4

# loop 2
2
2, 3
2, 3, 4

# loop 3
3
3, 4

# loop 4
4

여기서 무게를 함께 생각했었더라면...

 

반복문을 정교하게 사용해야하는데 파이썬으로 잘 구현하지 못하고 있어서 기존 생각이 맞는지 자바스크립트로 먼저 구현하며 체크해봤다.

let index = 0;
const limit = [10, 15, 50, 30];
let weights = [];

while(index != limit.length) {
    let cnt = 0;
    for (let i = index; i < limit.length; i++) {
      let weight = [];
      console.log(`줄의 갯수 = ${++cnt}`);
      for (let j = index; j <= i; j++) {
        weight.push(limit[j]);
      }
      // 들 수 있는 최대 무게 = 무게 안에서 가장 작은 값 * 무게 배열 갯수
      console.log(`로프들이 각각 견딜 수 있는 무게 : [${weight}]`);
      const answer = Math.min.apply(null, weight) * weight.length;
      weights.push(answer);
      console.log(`병렬로 견딜 수 있는 무게 = ${answer}`);
      console.log("============");
    }
    index++;
}

console.log(`정답 : ${Math.max.apply(null, weights)}`);

예제 출력을 테스트해보고 몇가지 테스트를 더 해본 결과 제대로 된 정답이 나왔다. 알고리즘의 방향성은 제대로 잡았다고 생각하고, 코드를 좀 더 정리하면서 파이썬으로 구현했다.

 

첫번째 시도 (실패 - 시간초과)

N = int(input())
limit = []
for _ in range(N):
		limit.append(int(input())

index = 0
weights = [] # 병렬로 연결된 로프들이 견딜 수 있는 무게가 저장
while index != N:
    # print(f'index = {index}')
    for i in range(len(limit)):
        rope = [] # 선택한 로프를 담을 배열, index가 증가하고 다시 들어올 때 초기화
        for j in range(i + 1):
            # print(f'limit[j] = {limit[j]}')
            rope.append(limit[j])
        
        result = min(rope) * len(rope) # 병렬로 견딜 수 있는 무게
        weights.append(result) # 최대 무게를 구하기 위해 배열에 담아둔다.

    del limit[0]

    index += 1

print(max(weights))

알고리즘이 정확하게 동작하길 바라서 최대한 신중히 코딩했지만 뭔가 파이썬스럽지 않은 난잡한 코드라고 생각됐다.

 

결과는 시간초과로 실패.

 

성능을 개선하기 위해 아는 지식을 총동원해서 리팩토링해보았다.

 

두 번째 시도 (실패 - 시간초과)

N = int(input())
limit = [int(input()) for _ in range(N)]

index = 0
nextIdx = 0
weights = [] # 병렬로 연결된 로프들이 견딜 수 있는 무게가 저장
while index != N:
    # print(f'index = {index}')
    for i in range(nextIdx, len(limit)):
        rope = [] # 선택한 로프를 담을 배열, index가 증가하고 다시 들어올 때 초기화
        for j in range(nextIdx, i + 1):
            # print(f'limit[j] = {limit[j]}')
            rope.append(limit[j])
        
        rope.sort()
        result = rope[0] * len(rope) # 병렬로 견딜 수 있는 무게
        weights.append(result) # 최대 무게를 구하기 위해 배열에 담아둔다.

    nextIdx += 1 # index로 처리해서 리스트 직접 제거로 인한 성능저하를 방지해준다
    index += 1

weights.sort()
print(weights[-1])

min, max 함수는 지난번 문제를 해결할 때 sort보다 느린 경우가 있어서 혹시나 하는 마음에 바꿔주었고 리스트에서 직접 제거하는 방식이 아닌 인덱싱으로 처리해서 시간복잡도를 조금은 줄일 수 있도록 해보았다.

(딱히 코드가 파이썬스러워진거 같지도 않다..)

 

아주 약간 성능이 향상된 것으로 보였지만 여전히 시간초과가 발생했다 ㅠ

 

코드에 정렬이 너무 많이 나와서 생기는 문제인가 싶어서 문제 해결 방법을 바꿔보기로 했다.

처음부터 로프들이 담긴 배열을 정렬하고 계산을 하는 것이다.

# ex)
N = 4
rope = [100, 40, 15, 10] # 내림차순 정렬

# loop 1
100 # 100
100, 40 # 80
100, 40, 15 # 45
100, 40, 15, 10 # 40

# loop 2 (첫 루프 중에 정답이 있으므로 더 이상의 반복은 의미가 없다)
40 # 40
40, 15 # 30
40, 15, 10 # 30
..., n번째 수 m # W(견딜 수 있는 무게) = m * n

 

모든 로프를 담은 배열 rope = []를 내림차순하게 될 경우는 다음과 같이 적을 수 있다.

W(견딜 수 있는 무게) = rope[idx] * (idx + 1)

이 경우 idx + 1 이 선택한 로프의 갯수와 같기 때문에 시간이 초과되었던 코드에서 로프를 직접 선택해주는 과정을 생략할 수 있게 된다.

또한 이제껏 작성했던 코드는 항상 마지막까지 돌고 정답을 알아내기 때문에 시간초과가 뜬다는 것을 알 수 있었다.

다시 코딩해보자.

N = int(input())
rope = [int(input() for _ in range(N)]

rope.sort(reverse=True)

weights = []
for idx in range(N):
	weights.append(rope[idx] * (idx + 1)

print(max(weights))

코드의 길이가 획기적으로 줄었다!

 

파이썬 반복문의 형식을 이용해서 더욱 줄인다면 다음처럼 쓸 수 있다.

N = int(input())
rope = [int(input()) for _ in range(N)]

rope.sort(reverse=True)
weights = [(rope[idx] * (idx + 1)) for idx in range(N)]

print(max(weights))

 

처음 문제를 보고 고민하며 얻은 공식은 다음과 같았다.

W(견딜 수 있는 무게) = 가장 작은 무게를 견딜 수 있는 로프 * 선택한 로프의 갯수

위 방법을 알아내고 푼 방식은 새로운 배열을 만들어서 선택한 로프를 담고 탐욕법으로 모든 경우의 수를 계산하는 것이였다.

아무리 탐욕법이라지만 굳이 전부 계산할 필요는 없었는데 너무 어렵게 생각했던거 같다.

 

Reference

• https://www.acmicpc.net/problem/2217