백준 2217 - 로프 ( Python )

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

2217번: 로프

예제풀이

n: 2
10
15

2개의 로프가 각각 10 15를 들 수 있음.
10인 로프는 10이 넘어가는 순간 끊어짐

예제의 최대 무게는 20이된다.

n: 5
3

7

1

10

5

이런경우에는 줄을 5개를 쓰는 것이 불필요하다
1이 5개인 경우엔 고작 5까지밖에 못들지만
최대가 10이므로 하나를 쓰는게 더 나은 경우다

내림차순으로 정렬해보자

모든 경우의 수를 생각해보면

10 -> 10
7 -> 14
5 -> 15
3 -> 12
1 -> 5

여기서 규칙을 찾을 수 있다

 

10 => 10 *1( index 0 ) : 10

7 => 7 * 2 ( index 2 ) : 14

5 => 5 * 3 ( index 3 ) : 15

3 => 3 * 4 ( index 4 ) : 12

1 => 1 * 5 ( index 5 ) : 5

 

오름차순으로 정렬한 경우 index 값+1을 곱해주면 해당 로프의 최대 무게를 구할 수 있다.

각 값을 배열에 넣어서 max값을 뽑아주거나(정수가 10000까지 밖에 안되므로 가능한일)

아니면 반복문마다 max값을 비교해서 max값을 리턴해주자

 

하지만 처음에는 index규칙을 생각못하고 바로 반복문을 돌려버려서

메모리 초과가 나왔다.

n = int(input())
maxWeight =[int(input()) for i in range(n)]
maxWeight.sort(reverse=True)
weightList = []

for (idx, i) in enumerate(maxWeight):
    for j in range(idx + 1):
        weight = (j+1) * i
        weightList.append(weight)
print(max(weightList))

 

1. 오름차순, 배열에 넣는 방식으로 풀이 (enumerate사용)

n = int(input())
maxWeight =[int(input()) for i in range(n)]
maxWeight.sort(reverse=True)
weightList = []

for (idx, i) in enumerate(maxWeight):
    weight = i * (idx + 1)
    weightList.append(weight)
print(max(weightList))

채점시간이 너무 오래 걸려서 뭐가 잘못된줄 알았는데 input()을 써서 그런거엿음

 

2. 내림차순, 배열에 넣는 방식으로 풀이

n = int(input())
maxWeight =[int(input()) for i in range(n)]
maxWeight.sort()
weightList = []

for i in maxWeight:
    weight = i * n #enumerate를 사용한 인덱스 값은 필요없고 n으로 해결가능
    weightList.append(weight)
    n -=1
print(max(weightList))

 

3. 내림차순, max비교 방식으로 풀이

import sys
inp = sys.stdin.readline

n = int(inp())
maxWeight =[int(inp()) for i in range(n)]
maxWeight.sort()
maxResult = 0

for i in maxWeight:
    weight = i * n
    n -=1
    if weight > maxResult:
        maxResult = weight
print(maxResult)

시간은 2,3번이 비슷하나 3번이 메모리 차지가 적으므로 제일 최적의 풀이법이 아닐까 한다.

물론 더 간편하게 풀이하신 분들도 있겠지만...