2217. [Python]로프

1. 문제

 

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

2217번: 로프

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 192MB
• 리스트 정렬, 탐색

 

3. 파이썬 코드

 

N = int(input())
# 로프 리스트 생성
lope_list = []

for _ in range(N):
    lope_list.append(int(input()))

# 로프 리스트를 큰순으로 정렬함 내림차순(큰거=>작은거)
lope_list.sort(reverse=True)

# check 라는 변수로 시작할때 값을 설정
check = 0
# max_weight로 값 설정
max_weight = 0

for i in range(N):
# 만약 시작하는 값이면
    if check == 0:
# min_num 에 리스트 처음 요소를 넣어준다.
        min_num = lope_list[0]
# check 라는 변수에 값을 넣어 처음이 아닌 것을 나타냄
        check += 1
# max_weight 에 min_num * i 를 해준다. => min_num * i 해주는 이유는 로프의 개수에 따라서 받는 하중이 달라지기 때문이다.
        max_weight = min_num * 1
    else:
# min_num값이 lope_list 리스트를 순회하며 최소값인지 판단
        if min_num > lope_list[i]:
            min_num = lope_list[i]
# min_num값의 최대 중량이 max_weight 보다 큰 경우 max_weight 값에 넣어줌
        if max_weight < min_num*(i+1):
            max_weight = min_num*(i+1)
print(max_weight)

 

4. 문제를 풀고난 후 생각

 

• 문제를 처음보고 문제를 이해하는데 많은 시간이 들였던 문제였던 것 같다.
• 문제에서 요구하는 W(중량)을 계산하는 방법을 어떻게 구현할지 고민이 됐던 것 같다.
• 처음 들었던 생각은 로프를 모두 사용해서 최대 중량을 구해야 하는 것이라고 생각을해서 그렇게 구현을 했고, 반례들을 찾아보니 답이 맞지않아서 생각을 다시 해보게 되었다.

주어진 로프를 모두 사용하는 것이 아닌 일부를 사용해서 최대 중량을 구할 수 있다.

ex)

3개의 로프가 주어져있고 1, 5, 9 의 최대 중량을 들 수 있는 로프들이 주어졌다. 들 수 있는 최대중량이 얼마인지 계산해보자.

• 9 를 선택하면 들 수 있는 최대중량 9 ( 9 * 1)
• 5,9 를 선택하면 들 수 있는 최대중량 10 ( 5 * 2 )
• 1,5,9를 선택하면 들 수 있는 최대중량 3 (1 * 3)

왜 이런 중량이 나오는지 설명하자면 중량이 로프의 갯수만큼 나눠지기 때문에 각각 로프가 감당가능한 하중이 5, 9 이런식으로 주어져있다면 'W가 12일 경우 각각 로프에 6, 6의 중량이 걸리기 때문에 최대 중량인 5를 넘겨버리게 된다.' 이러한 제약 때문에 기준을 낮은 숫자를 기준으로 최대 중량으로 계산을해야 로프가 중량을 감당할 수 있다. 

• 최대 중량을 구하는 기준이 최소 중량이 되면서 높은 중량을 가져야 하기 때문에 N번의 반복문을 시행해가며 로프의 개수가 늘어나며 높은 중량을 가지는 것을 찾아내는 것을 구현했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 그리디 알고리즘