[그리디] 백준 Silver 4 로프(Python 파이썬)

💡문제 링크

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

 

💡문제 분석 요약

1. 로프의 개수 n

2. 각 로프가 버틸 수 있는 무게 제시

3. 로프 여러 개로 하나의 물체를 들 수 있음

4. 모든 로프를 사용할 필요 없고, 임의로 몇 개의 로프만 사용해도 된다.

5. k개의 로프를 선택하면, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

6. w/k의 최댓값을 구하는 문제!

 

💡알고리즘 설계

1. for문을 사용해서 모든 로프가 버틸 수 있는 무게 정보를 rope 리스트에 담기

2. rope 리스트를 오름차순으로 정렬

3. rope 리스트를 앞에서부터 탐색하며 최대 중량을 찾기

4. 최대 중량 출력

 

💡코드

n = int(input())
rope = []
for _ in range(n):
    rope.append(int(input()))
rope.sort()

answer = 0
for i in range(n):
    if answer < rope[i] * (n-i):
        answer = rope[i] * (n-i)
print(answer)

n = int(input())
# 각 로프가 버틸 수 있는 무게 입력받고, 오름차순으로 정렬
rope = []
for _ in range(n):
    rope.append(int(input()))
rope.sort()

# answer를 갱신해가면서 최대 중량을 찾기
answer = 0
for i in range(n):
    if answer < rope[i] * (n-i):
        answer = rope[i] * (n-i)

# 결과 출력
print(answer)

💡 오답 풀이

모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

처음에는 당연히 "모든 루프를 사용해야 최대 중량이 될 것이다"라고 생각했는데, 아니었다.

예를 들어 로프가 4개 있고 각각이 버틸 수 있는 무게가 [5, 7, 9, 10]이라고 할 때 모든 로프가 버틸 수 있는 최대 무게는 20이고, [7, 9, 10] 3개의 로프로 버틸 수 있는 무게는 21로 이게 더 크다.

따라서 무작정 rope 리스트에서 최솟값 찾고 그 최솟값에 n을 곱했는데, 틀렸다...

자세히 찾아보니 저런 조건이 있었고, 이를 고려해서 다시 코드를 짰다.

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

코드를 짜면서 '아 이런 유형이 그리디구나. 무작정 앞에서부터 탐색하는 게 그리디 유형이구나~'를 깨달음.