Algorithm-기타리스트

문제유형 :
- 동적 프로그래밍
설명
- 벽돌의 수가 N개일 때, 시간복잡도 O(N^2)
- 벽돌의 번호를 출력해야함 -> 계산된 테이블 역추적 가능해야함
- 먼저 벽돌을 무게 기준으로 정렬
- D[i] = 인덱스 i인 벽돌을 가장 아래에 두었을 때의 높이
- 모든 0 <= j < i에 대해, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]
- 이후에 Max Value에서 테이블 역추적

풀이

    n = int(input())
    array = []

    array.append((0, 0, 0, 0))
    for i in range(1, n + 1):
        area, height, weight = map(int, input().split())
        array.append((i, area, height, weight))

    array.sort(key=lambda data: data[3])

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(0, i):
            if array[i][1] > array[j][1]:
                dp[i] = max(dp[i], dp[j] + array[i][2])

    max_value = max(dp)
    index = n
    result = []

    while index != 0:
        if max_value == dp[index]:
            result.append(array[index][0])
            max_value -= array[index][2]
        index -= 1

    result.reverse()
    print(len(result))
    [print(i) for i in result]

Algorithm-기타리스트

Yechan Kim