논문 작업과 추석 연휴로 인해 오랜만에 돌아왔네요.. 물론 이 글을 작성하는 지금도 연휴 기간입니다.
오늘 문제는 처음에 접근이 쉽지 않았던 문제입니다. 살펴볼까요?
1. 오늘의 학습 키워드
- 그리디 알고리즘
2. 문제: 로프 (2217번)
- 단계: 🥈 실버4단계
- 유형: 수학, 그리디 알고리즘, 정렬
- 출처: https://www.acmicpc.net/problem/2217
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 192 MB | 71089 | 31753 | 25404 | 43.596% |
문제
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1 복사
2
10
15
예제 출력 1 복사
20
출처
알고리즘 분류
3. 나의 풀이
문제 이해 및 접근
이 문제는 여러 개의 로프를 사용하여 물체를 들어올릴 때, 들어올릴 수 있는 최대 중량을 구하는 문제입니다. 각각의 로프는 다르게 설정된 최대 중량을 견딜 수 있으며, 여러 로프를 병렬로 사용하면 그 중량이 고르게 분배됩니다. 따라서, 각 로프는 같은 중량을 나누어 가지게 되며, 이를 고려하여 들어올릴 수 있는 최대 중량을 계산해야 합니다.
핵심은 가장 약한 로프가 감당할 수 있는 중량을 기준으로 여러 개의 로프를 사용할 수 있다는 점입니다. 여러 로프를 선택했을 때 그 중 가장 약한 로프가 기준이 되기 때문에, 그리디 알고리즘을 통해 이 문제를 해결할 수 있습니다.
접근 방법
- 로프를 오름차순 정렬: 중량을 적게 버틸 수 있는 로프부터 정렬하여 계산합니다.
- 최대 중량 계산: 각 로프를 기준으로 사용할 수 있는 로프의 개수를 곱하여 들어올릴 수 있는 중량을 계산합니다.
- i번째 로프를 사용할 때의 최대 중량은
로프[i] * (남은 로프의 개수)로 계산할 수 있습니다. - 즉, 약한 로프일수록 그 로프를 포함한 로프들이 견딜 수 있는 최대 중량이 결정됩니다.
- i번째 로프를 사용할 때의 최대 중량은
코드 설명
import sys
def sol(N, lope):
ans = [] # 각 경우의 들어올릴 수 있는 중량을 저장할 리스트
lope.sort() # 로프의 중량을 오름차순 정렬
# 각 로프를 기준으로 가능한 최대 중량 계산
for i in range(N):
ans.append(lope[i] * (N - i)) # 로프[i] * 남은 로프 수
return max(ans) # 들어올릴 수 있는 최대 중량 반환
# 입력 처리
N = int(sys.stdin.readline().strip())
lope = [int(sys.stdin.readline().strip()) for _ in range(N)]
# 결과 출력
print(sol(N, lope))
풀이 과정
- 정렬: 로프의 최대 중량을 오름차순으로 정렬합니다. 이렇게 하면 가장 약한 로프부터 차례대로 접근할 수 있습니다.
- 최대 중량 계산:
lope[i] * (N - i)는i번째 로프를 포함한 남은 모든 로프가 들어올릴 수 있는 최대 중량을 의미합니다. 즉, 약한 로프일수록 그 로프를 포함한 로프들이 견딜 수 있는 최대 중량이 결정됩니다.
- 최대값 반환: 모든 경우에서 들어올릴 수 있는 중량을 리스트에 저장한 후, 그 중 가장 큰 값을 반환합니다.
시간 복잡도
- 정렬:
lope.sort()는 O(N log N)의 시간 복잡도를 가집니다. - 최대 중량 계산: 각 로프에 대해 한 번씩 최대 중량을 계산하므로 O(N)의 시간이 소요됩니다.
따라서 전체 알고리즘의 시간 복잡도는 O(N log N)입니다.
예시
예제 입력 1
2
10
15
예제 출력 1
20
설명: 두 개의 로프를 사용할 경우, 각 로프에 걸리는 중량은 10kg와 15kg이므로, 두 로프를 사용한 최대 중량은 10 * 2 = 20kg입니다.
예제 입력 2
3
5
10
15
예제 출력 2
20
설명: 세 개의 로프 중에서 가장 약한 로프인 5kg를 포함한 경우에 최대 중량은 5 * 3 = 15kg입니다. 그러나 두 번째로 약한 로프인 10kg를 포함한 두 개의 로프를 사용할 경우 최대 중량은 10 * 2 = 20kg으로, 더 큰 중량을 들어올릴 수 있습니다.
마무리
이번 문제는 그리디 알고리즘을 활용하여 로프의 최대 중량을 최소화하면서도 최대 중량을 계산하는 문제였습니다. 그리디 방식으로 로프를 정렬한 후, 각 로프를 기준으로 사용할 수 있는 로프의 개수를 곱하여 최대 중량을 계산하는 방식은 매우 효율적이었으며, 이를 통해 O(N log N)의 시간 복잡도로 문제를 해결할 수 있었습니다.
이 문제를 통해 정렬과 그리디 알고리즘의 중요한 개념을 복습할 수 있었고, 다양한 문제에서 적용할 수 있는 해결 방법을 배울 수 있었습니다.
읽어주셔서 감사합니다!
풍요로운 한가위 되세요~~
추석에도 달리는 나!
