[백준] 2217번 로프 파이썬 해설

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

2217번: 로프

그리디 알고리즘으로 분류된 문제이다.

그리디 알고리즘의 정의는 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘이다.

문제에 적용시켜보자.

 

풀이

---

먼저 문제의 조건을 잘 읽어야 한다.

"모든 로프를 사용해야 할 필요는 없으며"

이 말은 로프가 두 개 주어지고 두 로프가 버틸 수 있는 최대 중량이 1, 10이라면

굳이 두 개의 로프를 사용하지 않고 두 번째 로프만 사용하는 것이 더 많은 중량을 버틸 수 있다.

 

-정답 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    arr = []

    for i in range(N):
        arr.append(int(input()))
    arr.sort(reverse=True)

    m = 0
    for i in range(len(arr)):
        temp_max = arr[i] * (i+1)
        if temp_max > m:
            m = temp_max

    print(m)

먼저 리스트 arr에 모든 입력을 받은 뒤 내림차순으로 정렬한다.

반복문 안에서는 다음과 같은 동작을 한다.

1) i = 0일 때 : 가장 최대의 중량을 버틸 수 있는 로프의 정보 x 1

2 - 1) i = 1일 때 : 두 번째로 많은 중량을 버틸 수 있는 로프의 정보 x 2

2 - 2) i = 0 일 때와 비교하여 더 많은 양의 중량을 m값에 저장.

3) 리스트 arr의 길이만큼 반복.

 

위 반복문이 끝나면 m에는 주어진 조건에서 가장 많이 버틸 수 있는 중량이 저장된다.

 

결과

---

이번 문제는 한 번의 시도만에 맞아서 괜히 기분이 좋아지는 문제였다. ㅎㅎ

블로그를 운영한 지 얼마 되지 않아서 나만의 프레임이 없다.

매번 새로운 프레임으로 예쁘게 정리해보려고 노력 중이다.