백준 2217 로프 Python 3

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

2217번: 로프

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2217.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_maximum_weight(N, rope):
    weight = rope[0]
    for i in range(1, N):
        if rope[i]*(i+1) > weight:
            weight = rope[i]*(i+1)
    print(weight)

input = sys.stdin.readline
N = int(input())
rope = list()
for _ in range(N):
    rope.append(int(input()))
rope.sort(reverse=True)
get_maximum_weight(N, rope)

---

풀이 과정

풀이 시간 21분

들 수 있는 물체의 중량이 다른 N개의 로프 중 임의로 몇 개를 사용하여 들 수 있는 최대 중량을 구하는 문제이다.

따라서 N개의 로프를 모두 사용해도 되고 일부만 사용해도 되는 점이 핵심이다.

그리고 k개의 로프를 사용해서 중량이 w인 물체를 들어 올린다면 각 로프에는 w/k 만큼의 중량이 걸린다.

따라서 들 수 있는 중량이 큰 순서대로 로프를 정렬하고 차례대로 탐색하면서 현재 로프를 선택할지 말지를 판단하도록 알고리즘을 짰다.

현재 로프를 선택했다면 이후에도 해당 로프를 선택한 것이 최대가 되기 때문에 로프를 선택하는 매순간 최대의 결과를 만들어 나가면 최종적으로 답을 구할 수 있다.

때문에 항상 최선의 선택을 해나가는 것이 최종적으로 최적의 해를 만들어 나가는 그리디 알고리즘이 적용된다.

import sys
def get_maximum_weight(N, rope):
	#가장 무거운 중량을 드는 로프를 선택한 것으로 초기화
    weight = rope[0]
    
    for i in range(1, N):
    	#i번째 로프까지 선택했을 때가 기존에 선택한 로프로 들 수 있는 중량보다 큰 경우,
        if rope[i]*(i+1) > weight:
        	#i번째 로프까지 선택한다
            weight = rope[i]*(i+1)
            
    print(weight)

input = sys.stdin.readline
N = int(input())
rope = list()
for _ in range(N):
    rope.append(int(input()))
    
#들 수 있는 중량이 큰 순서대로 로프를 정렬한다 -> 내림차순 정렬 O(Nlog N)
rope.sort(reverse=True)
get_maximum_weight(N, rope)

#시간복잡도 = O(nlog n), 공간복잡도 = O(n)