백준 / 로프 / 2217번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 로프 / 2217번 (실버 4단계)

문제 사이트: https://www.acmicpc.net/problem/2217

 

문제 설명

---

나의 풀이

# 로프의 개수
n = int(input())

# 최대 중량을 구하는 변수
max_weight = 0
# 로프를 저장하는 배열
rope = [int(input()) for _ in range(n)]

# 내림차순으로 저장
rope.sort(reverse = True)

# 이전 무게
current_weight = rope[0]

for i in range(1, n):
    # 이후 무게
    next_weight = rope[i] * (i + 1)
    if current_weight > next_weight:
        max_weight = current_weight
        break
    else:
        current_weight = next_weight
        max_weight = current_weight

print(max_weight)

그리디한 방식을 생각했을 때 현재의 중량과 다음의 중량과 비교하여 만약 현재가 더 많게되면 종료하면 될 것 같은 생각이 들어서 풀었지만 반례가 생겼다.

예를 들어

15 10 5 5 5 5 5 5의 경우에서는 0번째 15, 1번째 20이지만 2번째에서 15가 된다. 하지만 모든 로프를 사용하게되면 최대 중량은 40이다. 이 경우의 수를 고려하지 않은 풀이 방법이었다.

# 로프의 개수
n = int(input())

# dp
dp = [0] * 100001
# 로프를 저장하는 배열
rope = [int(input()) for _ in range(n)]

# 내림차순으로 저장
rope.sort(reverse = True)

# 이전 무게
current_weight = rope[0]
# 각 상황의 무게를 측정
dp[0] = rope[0]

for i in range(1, n):
    # 이후 무게
    next_weight = rope[i] * (i + 1)
    dp[i] = next_weight

# 최대 중량을 구하는 변수
max_weight = max(dp)

print(max_weight)

위 풀이는 메모이제이션을 이용한 이전의 결과 값을 저장해서 비교하는 방법이다.

---

※ 알아야 할 것

메모이제이션이란 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.