[BOJ] 2217 - 로프 (🥈 실버 4티어)

사용 언어: Python3

문제

로프

풀이

나의 풀이 - DFS

import sys
sys.setrecursionlimit(10**6)

N = int(input())
ropes = [int(input()) for _ in range(N)] # 주어진 로프들

def DFS(L, lst): # lst: 사용하기로 선택한 로프들
    global mx
    print(L, lst)
    if lst and min(lst) * len(lst) > mx:
        mx = min(lst) * len(lst)
    if L == N:
        return
    DFS(L+1, lst + [ropes[L]]) # 로프 선택
    DFS(L+1, lst) # 로프 선택 X
    
mx = -1e9
DFS(0, [])
print(mx)

• 테스트 케이스: 성공
• 제출 결과: 메모리 초과 🥵

다른 풀이 - 그리디

참고

N = int(input())
ropes = [int(input()) for _ in range(N)]

ropes.sort(reverse=True) # ✅ 정렬

mx = -1e9
for i in range(N):
    mx = max(mx, ropes[i]*(i+1)) # ✅ (로프가 버틸 수 있는 무게) * (사용란 로프 개수)
print(mx)

• 테스트 케이스: 성공
• 제출 결과: 성공
• 로프를 내림차순 정렬한 뒤에 그리디로 풀 수 있다!
• N개의 로프를 사용해 중량이 w인 물체를 들어올린다면 각 로프에 w/N만큼의 중량이 걸린다고 했다.
  • 각 로프가 버틸 수 있는 무게가 T라고 할 때, 물체의 최대 중량(w)는 w = T * k이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기