[Baekjoon, Python] 2217번 : 로프

도입

백준 알고리즘 분류-그리디 알고리즘 여덟 번째 문제이다.

백준 2217번 문제, 입력, 출력

---

백준 2217번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 일단 최대중량을 어떻게 구하는지 알아야 한다. 예제에서 처럼 10, 15 중량을 견디는 로프가 있다면 2개의 로프를 사용하여 견딜수 있는 최대중량은 20이다. 2개의 로프중 가장 작은 중량 10에 개수 2를 곱하면 된다. 또 다른 예제로, 10, 15, 20 중량을 견디는 3개의 로프가 있다면 3개의 로프를 사용하여 견딜 수 있는 최대 중량은 30이다. 가장 작은 중량 10에 개수 3을 곱하면 된다.

 

2. 경우의 수를 따질 필요가 있다. 10, 15, 20 중량의 로프가 있다고 하자. 문제에서는 3개의 로프를 전부 사용해서 최대중량을 구하라는 말이 없다. 그렇다면, 1개의 로프를 사용했을 때 최대중량, 2개의 로프를 사용했을 때 최대중량, 3개의 로프 모두를 사용했을 때 최대중량 총 3가지의 경우가 있다. 이 3가지의 경우에서 최대값이 10, 15, 20 로프를 사용했을 때 가질 수 있는 최대값이다.

 

3. 로프를 배열로 받아서 내림차순으로 정렬하면 계산이 쉽다. 10, 15, 20의 로프가 있다고 치자. 1개를 사용 한다면 최대중량은 어느 로프를 사용했을 때인가? 당연히 20의 로프를 사용할 때이다. 그렇다면 2개를 사용 한다면 최대 중량은 어느 로프를 사용했을 때인가? 당연히 15, 20을 사용했을 때이다. 그렇다면 배열을 20, 15, 10으로 내림차순으로 정렬한 뒤 경우의 수대로 비교를 하면 계산이 훨씬 간편해 진다.

---

코드

from sys import stdin

var_N = int(stdin.readline())  # 1 <= N <= 100000
list_rope = []
list_max_w = []

for i in range(var_N):
    list_rope.append(int(stdin.readline()))

list_rope.sort(reverse=True)

for i in range(var_N):
    list_max_w.append(list_rope[i]*(i+1))

print(max(list_max_w))

---

마무리

 문제를 읽고 바로 이해하지 못했다. 주어진 개수의 로프를 전부 사용하지 않는 경우에 대한 고민이 있었다.