백준 2217번 <로프>

백준 알고리즘 2217번

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

2217번: 로프

---

2217번

각 로프는 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 다르다. K개의 로프를 사용하여 중량이 W인 물체를 들어올릴 때, 각각의 로프는 모두 고르게 W/K 만큼의 중량이 걸리게 된다.

각 로프가 들어올릴 수 있는 물체의 최대 중량이 주어졌을 때, 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구하여라. 이때, 모든 로프를 사용해야 할 필요는 없다.

 

입력으로 첫 줄에 로프의 수 N이 들어오고 그 다음 N개의 줄에 걸쳐 각 로프가 들어올릴 수 있는 물체의 최대 중량이 주어진다.

 

출력으로는 주어진 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 출력하면 된다.

---

문제 해결

이 문제는 그리디 알고리즘으로 해결할 수 있다.

 

1. 로프가 들어올릴 수 있는 물체의 최대 중량의 최솟값 * N

2. 그 다음 최솟값 * ( N - 1번에서의 최솟값 로프의 개수)

3. 그 다음 최솟값 * ( N - 1번에서의 최솟값 로프의 개수 - 2번에서의 최솟값 로프의 개수)

...

이렇게 구해서 이 중 최댓값을 반환하면 된다.

 

먼저 로프를 입력받는데 dictionary를 이용하여 key를 로프가 들어올릴 수 있는 물체의 최대 중량으로 하고 value를 해당 로프의 개수로 하여 정리하였다.

 

그 후에 key를 기준으로 내림차순 정렬하였다.

 

maxWeight에 들어올릴 수 있는 물체의 최대 중량이 가장 작은 중량 *  N을 저장한다. 

로프의 개수를 count하기 위해 cnt 변수에 N을 저장하였다.

 

정렬되어 있는 sort_loop를 for문을 돌려서 최소 최대 중량 * cnt 값이 maxWeight보다 크다면 maxWeight값을 update하고 cnt에 해당 로프의 개수를 빼서 update하였다.

---

코드

N = int(input())

loop = {}
for i in range(N):
    t = int(input())
    if t in loop:
        loop[t] = loop.get(t) + 1
    else:
        loop[t] = 1

sort_loop = sorted(loop.items(), key = lambda item : item[0])

maxWeight = sort_loop[0][0] * N
cnt = N
for key, value in sort_loop:
    if cnt == N:
        cnt -= value
        continue
    chk = key * cnt
    if chk > maxWeight :
        maxWeight = chk
    cnt -= value         
    
print(maxWeight)

---

결과

---