[#2217] 로프

2217번: 로프

 

아주 간단한 그리디 문제... 인줄 알았으나 지나치게 그리디하게 풀어서 메모리 초과
최대한 간단명료한 발상을 해보도록 노력하자

 

오늘 dp 이론이랑 예전에 풀어놨던 예제를 더 공부해야할것같아서 30분컷 목표로 간단한 문제를 풀었다!

 

 

 

---

 

 

예제로 이해하기

 

가설1 : 모든 로프를 다사용하는것이 최적을 보장)

예제의 경우는 그렇게 적용된다. 

10, 15 로프가 있으면

x / 2 = min(10, 15) = 10

그러므로 x = 20

 

하지만 반례로서, '모든 로프를 다 사용하는것이 최적이 아닌 경우' 가 있다. 

 

100, 1, 1, 1, 1 로프가 있을때

모든 로프를 사용하는 것은 x/5 = 인데, x = 5여야지 1로프가 이를 견딜 수 있게 된다. 

고로, 답은 5가 된다. 

 

하지만 100 로프만 사용하는 경우 x/1 = 100 이어도 100로프는 이를 견딜 수 있으므로

답은 100이 된다.

 

따라서 반례로서, "모든 로프를 다 사용하는 것이 최적을 보장한다" 는 틀림을 알 수 있다. 

 

 

 

 

가설 2 : 모든 케이스를 검토하는 경우)

정답 예제도 이렇게는 풀 수 있다.

case 1) 10로프만 사용 - > 최대 가능 중량 =>  x/1 = 10 이므로 x = 10

case 2) 15로프만 사용 - > 최대 가능 중량 =>  x/1 = 15 이므로 x = 15

case3) 10, 15로프 사용 -> 최대 가능 중량 => x/2 = 10 이므로 x=20

 

정답이 나옴을 보장하긴한데,, 시간복잡도가 괜찮을까? 검증해보고 코드를 세우도록 하자. 

 

 

시간복잡도 미리 짐작

 

N개의 로프 중 1,2,3,....,N개의 조합을 모두 검토하여 결과값을 비교해야한다. 

nC1, nC2, nC3, ... .nCn 마다 min() 연산이 걸린다. 

nCr의 시간복잡도는 N^2

 min()함수의 시간복잡도는 N

이므로 총 N^3 의 무거운 연산이 걸릴 것 같다. 

 

문제는 로프의 갯수는  N(1 ≤ N ≤ 100,000) 라고 한다.

최악의 경우 100,000개의 로프가 제공되면

10^15 의 연산이 수행된다. 

 

1억(100,000,000=10^8) 번의 연산에 대강 1초가 걸린다. 

우리는 2초의 시간 제한을 가지고 있으므로, 10^16 안으로 연산을 마쳐야하는데 10^15 의 연산은 아슬아슬하게 이 안에 통과한다. 

 

맘에 들진 않지만  더 기똥찬 방법이 떠오르지 않으니 기릿해보자!

 

 

 

 

처음 짠 코드

from itertools import combinations

n = int(input())
rope_arr = [] # 로프 당 부하중량을 기록하는 리스트
for _ in range(n) :     
    rope_arr.append(int(input()))

# 모든 로프 조합의 경우 구하기
case_arr = [] # nC1, nC2, ... nCn 의 모든 comniation 경우를 담는 리스트
for i in range(1, len(rope_arr)+1) :    
    case_arr += list(combinations(rope_arr, i)) # nCi


# 모든 로프 조합에 대해 최대 중량 계산하기
max_limit = -1
for case in case_arr : 
    max_limit = max(max_limit, len(case) * min(case))# 예시) x / 2 = min(10, 15) = 10 

print(max_limit)

메모리초과..ㅎ

 

 

아놔! 메모리를 어떻게 더 줄일까 하다가

그냥 모든 케이스를 구할때마다 메모리에 따로 담지 않고, burden limit을 계산해보기로 했다. 

 

 

두번째 짠 코드

from itertools import combinations

n = int(input())
rope_arr = [] # 로프 당 부하중량을 기록하는 리스트
for _ in range(n) :     
    rope_arr.append(int(input()))

# 모든 로프 조합의 경우 구하기
max_limit = -1
for i in range(1, len(rope_arr)+1) :    
    tmp_case_arr = list(combinations(rope_arr, i)) # nCi 인 경우
    for case in tmp_case_arr :  # 모든 nCi 경우에 대해 max burden limit 계산
        max_limit = max(max_limit, len(case) * min(case))# 예시) x / 2 = min(10, 15) = 10 

print(max_limit)

 

 

 

이 시점에서 맞춰둔 30분 타이머가 끝났다. 아놔 !! 이렇게 시간끌줄이야

이젠 여기서 어떻게 개선해야할지 떠오르지 않는다. 

 

한수 배워요 🗿

 

n = int(input())
rope_arr = [] # 로프 당 부하중량을 기록하는 리스트
for _ in range(n) :     
    rope_arr.append(int(input()))

# 내림차순으로 정렬
rope_arr.sort(reverse=True)

max_burden_arr = [] # n개를 n번사용하는 모든 경우를 저장한다
for i in range(n) :
    max_burden_arr.append(rope_arr[i] * (i+1)) # n개를 n번 사용할때=최대 이므로

print(max(max_burden_arr))# 그 중 최댓값 = 정답

 

" 최적 조건 : n번째로 큰 수를 n번 곱하기 " 를 발견 하면 쉬운 문제였다. 

 

 

바로 떠올랐다면 좋았을텐데..

하하 안되면, 지나치게 그리디로 풀기전에

케이스를 주루룩 써두고 더 명료한 공통점이나 점화식을 발견해보려는 시도는 해보자.