Greedy Python 백준 BOJ2217 로프 코딩테스트 (10)

목차

서론

지난번엔 그리디 알고리즘에 대해 알아보았고 몇 문제들을 풀어보았다. 해당 포스팅이 궁금하면 여기로 가길 바란다. 이번에는 이어서 문제를 풀고자 한다. 백준에 나와있는 BOJ2217 로프에 대한 문제인데, 이 문제에 대한 링크는 여기로 가면 된다.

 

---

문제 조건

문제의 조건을 적어보겠다. 1. 로프의 길이와 굵기는 다르다. 2. 때문에 들어올릴 수 있는게 다르다. 3. 여러개의 로프는 연결 할 수 있고, 연결한 만큼 더 많은 중량을 들어올리기가 가능하다. 4.K개 로프를 사용해 W 중량 물체를 올릴 때,  각각에거 W/K만큼 중량이 걸린다. 아무튼 이 조건을 활용해서 들 수 있는 최대 중량을 구하는 것이다. 모두 사용안 해도 된다가 포인트 같다.

---

내 풀이

예시를 보면 2개가 있을때 10, 15를 각각 들 수 있으면 20개가 최대다. N/K가 최소값보다 크면 되는거 아닌가? 그리고 마지막을 총 들 수 있는 건 N*K로 하면 되지 않을까 싶지만 문제의 조건인 모두 안 사용하고 임의로 골라서 사용해도 된다가 걸린다.  3개가 있고 5, 10, 15가 있으면 어떨까. 내 생각대로 하면 5가 최소값이라 3*5 = 15가 되어야 하지만 사실 10, 20을 선택하면 20으로 이게 이득이다. 얠 어찌해야될까. 정렬 후 큰거부터 차례대로 저걸 해본다음에 평균 길이가 적어지는 순간에 STOP하고 이전껄로 한다면? 오호라 근데 이게 그리디인가? 머 아무튼 이걸로 짜보겠다.

 

# 1. 정렬 후

# 2. 큰거부터 차례대로 하나씩 stack에 추가하면서

       tmp와 result를 비교한다. tmp는 새로 만들어진 result로 마지막에 추가된애(이미 정렬되서 가장 작은 값임)*길이임.

# 3. 계속하다가 이전 tmp가 result 이전보다 더 작아지는 순간이 오면

# 4. 그때 stop하고 pop해서 이상적 stack만들고

# 5. 다시 result를 구하면 될듯 

s = [5,10,15]

l = len(s)

s = sorted(s) # 1. 정렬 후

tmp, result = 0, 0

new_s = []

for i in range(l):

    x = s.pop()

    new_s.append(x)

    tmp = new_s[-1]*len(new_s)

    if tmp >= result: 

        result = tmp

    else:

        new_s.pop()

        print(new_s[-1]*len(new_s))

   else:

    break

print(x*len(new_s))

 

후. 난 정말 이게 한계다. 처음에는 n/k를 비교했는데 도저히 안돼서 그냥 전체를 계산하면서 했다. 

---

정석풀이

해당 풀이는 이 강의에 나온다. 일단 사용할 로프의 개수를 정해두기로 가정하면 가장 긴놈을 선택하는 것이 맞다고 판단한다. 고로 최대 중량대로 정렬한 후, w[n-k]*k를 하면 끝이다. 나는 정말 고전했는데 이 강의에서는 딱히 할말이 없다면서 넘어간다. 눈물남.

아 이사람은 그냥 max로 했구나. 그니까 sort를 하고, answer와 w[n-i]*i와 비교했다. 나처럼 pop()할 필요가 없었다는 뜻. 하하. 배열이 정해졌으니, 앞에 값과 비교하며 max값을 다 돌린거다 기껏해야 한바퀴니 그냥 다 돌린듯 하다. 이걸 파이썬 형식으로 바꾸면 다음과 같다.

s = [5,10,15]
l = len(s)
s = sorted(s) 
result = 0

for i in range(1, l + 1):
    result = max(result, s[l - i] * i)
print(result)

 너무 깔끔했군. 난 그동안 무엇과 고전했는가. 처음에 접근 방식은 바로 떠올랐다는 점에서 위안을 삼아야겟다. 아무튼 오늘은 여기까지 하고,  다음 포스팅에서는 DP 문제에 대해 다룰 예정이다. 내 코딩 테스트 준비 과정에 대해 궁금하신 분은 여기로.