[백준 온라인 저지] 로프

문제 출처

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

2217번: 로프

 

문제 요구사항

• N개의 로프를 주어지고 각각의 로프가 버틸 수 있는 최대 중량이 주어질 때, 로프를 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구하기

 

문제 아이디어

• 최대 중량을 로프의 갯수 * 로프의 최소 중량 값으로 진행
• 하지만, 위의 아이디어는 모든 로프를 이용한다는 전제 조건하에 각 로프에 물건의 무게 / 로프의 개수만큼 적용하기 때문에 맞다고 생각되었지만 로프의 최대 중량이 [1 ,1, 1, 5]로 주어진다면 답은 5짜리 로프 하나를 사용한 5가 답이 될 것이다.
• 따라서 전체 로프를 사용하는 것이 아닌 일부 로프만을 이용해서 최대 중량의 무게를 들어올릴 수 있도록 하자.
  • 주어진 로프의 중량을 오름차순으로 정렬을 먼저 시행.
  • [1, 2, 3, 4]의 로프 무게가 주어지고 반복을 통해 계산을 한다고 했을 때, 1에서는 1 * 4(1보다 큰 로프의 개수) 만큼 해주면 최대 중량이 될 것이다. 왜냐하면 로프 4개를 이용하고 각 로프에는 1씩의 무게를 나누게 하면 되고 그게 최대 중량이다.
  • 위의 방식을 이용해서 최대 중량을 찾아내면 될 것이다.

 

나의 풀이 (Python3)

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

import sys

N = int(sys.stdin.readline().strip())
ropes = []

for _ in range(N):
    ropes.append(int(sys.stdin.readline().strip()))

answer = 0
for i, r in enumerate(sorted(ropes)):
    answer = max([answer, (N-i) * r])
    
print(answer)

 

 

Github

• https://github.com/Limseunghyun95/Algorithm_study/commits/master/baekjoon/p_2217.py

GitHub - Limseunghyun95/Algorithm_study: 코딩 테스트 연습 공간