https://www.acmicpc.net/problem/2217
<<문제>>
N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
<<문제 해결>>
Greedy 알고리즘을 몇번 풀다보니 감이 잡혔다. 대부분 Sort와 같이 사용해서 해결하면 쉽게 해결할 수 있다.
여기서 파이썬 내장함수인 sorted를 사용하면 편리하다. sorted는 올림차순이고 내림차순을 하고 싶으면 sorted($,reverse=True) 를 하면 된다.
이 문제는 로프의 병렬로 연결했을때 로프의 중량 최대값을 구하는 문제이다.
여기서 주의할점은 로프를 연결했을때 연결한 로프중 가장 적은 값을 드는 로프로 계산해야 된다는 것이다.
예를 들어서, 10 15 로프 2개가 있을때 10로프는 10, 15로프는 15를 들 수 있지만 10 15 둘다 사용했을때 w/k이므로 20 이상들면 첫번째 로프가 무게를 감당할 수 없다.
즉, 연결한 로프 중 가장 최소로 드는 무게 * 연결한 로프 수 를 하면 된다.
이를 위해서 최대 중량을 구하기 위해서 로프가 들 수 있는 무게를 내림차순으로 정렬한다.
그 후 중량이 큰 순으로 로프를 추가하면서 계산하면 된다.
<<소스코드>>
N = int(input()) W=[] maxW=[]
for i in range(N): weight=int(input()) W.append(weight)
W=sorted(W,reverse=True)
for i in range(N): maxW.append(W[i]*(i+1))
print(max(maxW)) |
|
'Algorithm(알고리즘) > BOJ(백준) 문제풀이' 카테고리의 다른 글
백준 10610번 파이썬 풀이 | 30 | 그리디(Greedy) 알고리즘 (1) | 2020.07.07 |
---|---|
백준 2875번 파이썬 풀이 | 대회 or 인턴 | 그리디(Greedy) 알고리즘 (0) | 2020.07.04 |
백준 11047번 파이썬 풀이 | 동전 0 | 그리디(Greedy) 알고리즘 (0) | 2020.06.29 |
백준 1541번 파이썬 풀이 | 잃어버린 괄호 | 그리디(Greedy) 알고리즘 (0) | 2020.06.29 |
백준 11399번 파이썬 풀이 | ATM | 그리디(Greedy) 알고리즘 (0) | 2020.06.28 |