[Python_Greedy] 백준 2217번 : 로프

1. 문제

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

2217번: 로프

 

 

 

2. 풀이 과정

방법1)

(물건의 무게)/(로프의 수) ≤ (로프가 견딜 수 있는 무게) = (물건의 무게) ≤ (로프가 견딜 수 있는 무게)*(로프의 수)

n = int(input())
rope = [int(input()) for _ in range(n)]
rope.sort(reverse=True)

result = 0
for i in range(n):
  #로프 최소 무게 * 개수 <= 물건 무게
  result =max(result, rope[i]*(i+1))

print(result)

 

방법2)

[방법 1]보다 더 빠른 시간 내에 처리할 수 있다. sort함수를 쓰는 대신 배열에 넣으면서 정렬되도록 한다.

입력 값이 최대 10,000이기 때문에 사용할 수 있는 방법이다. 기본적인 개념은 Radix 정렬이 바탕이 된다고 볼 수 있다.

import sys
input = sys.stdin.readline

n = int(input())
rope = [0]*10001 #1~10000을 표현하기 위함

for _ in range(n):
  rope[int(input())] += 1 #해당 길이인 로프 수

result = 0
c = 0
for i in range(1, 10001):
  #로프 최소 무게 * 개수 <= 물건 무게
  if rope[10001-i] != 0:
    c += rope[10001-i]
    result =max(result, c*(10001-i))

print(result)