[BOJ] 2217: 로프

이슬비·2023년 2월 15일

Algorithm

목록 보기

83/110

내가 ! 시간 초과를 해결했다 !

1. 내 풀이 1: 실패

import sys
input = sys.stdin.readline

n = int(input())
rope_w = []
maxWeight = 0
for _ in range(n):
    rope_w.append(int(input())) 
rope_w = sorted(rope_w)

for i in range(len(rope_w)-1, -1, -1):
    maxWeight = max(maxWeight, rope_w[i]*len(rope_w[i:]))

print(maxWeight)

아이디어는 다음과 같다.

2, 10, 15

위 숫자들이 밧줄이 감당할 수 있는 중량이라고 해보자.
처음에는 제일 작은 중량을 n으로 곱해주면 되지 않을까 라고 생각했는데, 위의 경우에는 6이 아닌 10과 15의 로프만 사용하는 20이 답이 되어야 한다.

그래서 제일 끝에부터 for문을 돌면서 로프가 감당할 수 있는 현재 무게 * 사용한 로프의 개수 의 로직으로 풀 수 있도록 하였다.
이러한 로직을 위의 코드로 구현하면 답은 나오지만 시간 초과가 뜬다.

그 이유는 바로 len(rope_w[i:]) 때문이다.
매번 length를 새로 계산해주어야 하므로 시간이 많이 걸릴 수 밖에 없다.

2. 내 풀이 2: 성공

import sys
input = sys.stdin.readline

n = int(input())
rope_w = []
maxWeight = 0
for _ in range(n):
    rope_w.append(int(input())) 
rope_w = sorted(rope_w)
length = len(rope_w)
for i in range(len(rope_w)-1, -1, -1):
    maxWeight = max(maxWeight, rope_w[i]*(length-i))

print(maxWeight)

이를 미리 length 라는 변수로 전체 길이를 초기화 해주고, (사실 할 필요 없이 n을 바로 써도 됨)
그 후에 i를 빼주면서 길이를 구해주어도 동일한 로직을 갖게 된다.
그리고 시간 초과도 해결!

예전에 컴퓨터 시스템이라는 과목에서 함수를 계속 call 하면 러닝 타임이 길어질 거라는 개념을 배웠는데 ...!
여기서 이렇게 써먹게 될 줄은 몰랐다.

싸랑합니다 교수님.

3. 다른 풀이

def solution():
    answer = 0
    arr.sort(reverse=True)
    for i in range(N):
        arr[i] = arr[i] * (i + 1)
 
    return max(arr)
 
 
N = int(input())
arr = []
for _ in range(N):
    arr.append(int(input()))
 
print(solution())