Techbrad

[백준] 루프 파이썬 본문

Programming/코딩테스트

[백준] 루프 파이썬

brad.min 2023. 8. 31. 21:25
반응형

 

 

2217번: 로프

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하

www.acmicpc.net

문제 접근

로프의 개수와 들 수 있는 중량이 주어지고 가장 많이 들 수 있는 중량을 구하는 문제. 처음에는 단순히 15, 10 두개의 루프가 있을 때 15로 나누었을 때 1, 0 이면 15를 들 수 있고 10으로 나누었을 때 1, 1로 20을 들 수 있기 때문에 이러한 방식으로 풀려고 했다. 하지만 이러한 방식은 for 루프를 두번 돌리거나 코드가 복잡해 졌다. 결국 풀지 못하고 다른 코드를 참고 해 보았다....

 

알고리즘

그리디 알고리즘

 

코드

k = int(input())
rope = [int(input()) for i in range(k)]
result = []
for i, r in enumerate(sorted(rope, reverse=True)):
  result.append(r * (i+1))
print(max(result))

예를 들어 4, 6, 3, 1 라는 리스트가 주어진다면 내림차순으로 6, 4, 3, 1로 정렬한다. 이유는 6 중량으로는 하나의 로프만 가능하고 4 중량으로는 두개의 로프가 가능하다. 이런 규칙을 보았을때 리스트의 인덱스를 활용하여 6 * 1, 4* 2, 3*3, 1*4 이렇게 리스트의 요소와 인덱스를 곱하면 간단하게 구할 수 있다. 

 

역시 아직도 나는 한참 멀었다. 하지만 재밌다 ㅎㅎ

반응형