8.13 박스 쌓기

문제

너비 w, 높이 h, 깊이 d인 박스 n가 있다. 상자는 회전시킬 수 없으며, 다른 상자 위에 올려 놓을 수 있다.

단, 아래 놓인 상자의 너비, 높이, 깊이가 위에 놓인 상자의 너비, 높이, 깊이보다 더 클 때만 가능하다. 

이 상자들로 쌓을 수 있는 가장 높은 탑을 구하는 메서드를 작성하라.  탑의 높이는 탑을 구성하는 모든 상자의 높이다.

 

접근법

우선 박스들을 한번 정렬하고나면 다음 박스를 고를때 이전 박스를 돌아볼 필요가 없다. 

그래서 박스들을 너비, 높이, 깊이중 하나로 정렬을 하고나서, 

올려놓을 수 있는 상자를 순차적으로 올려놓아보면서 최대 높이를 구할 수 있다.

def Solution(boxes):
    boxes.sort()
    box_memo = [-1]*len(boxes)
    max_height = 0
    for i in range(len(boxes)):
        max_height = max(createStack(boxes, i+1), max_height)
    return max_height

def canbeabove( boxes, index , cur_i ):
    return  boxes[index][0] < boxes[cur_i][0] and boxes[index][1] < boxes[cur_i][1] and boxes[index][2] < boxes[cur_i][2]


def createStack(boxes, index, box_memo):
    if box_memo[index] >=0 :
        return box_memo[index]
    
    max_height = 0
    for i in range(index+1, len(boxex)):
        if canbeabove(boxes, index , i):
            max_height = max(max_height, createStack(boxes,i))
    
    max_height += boxes[index]
    box_memo[index] = max_height
    return max_height

2번째 방법은

 각 박스들을 올려 놓는 경우, 올려 놓지 않는 경우가 있을 것이다. 

그 상자를 올려 놓았을때의 높이와 올려 놓지 않은 경우의 높이중에 최대 값들의 합이 최대 높이가 될 것이다.

def Solution(boxes):
    boxes.sort()
    box_memo =[0]*len(boxes)
    max_height = createStack(boxex, -1, 0, box_memo)
    return max_height

def canbeabove( boxes, cur_i , next_i ):
    return  cur_i <0 or ( index(boxes[index][0] < boxes[next_i][0] and boxes[index][1] < boxes[next_i][1] and boxes[index][2] < boxes[next_i][2])

def createStack(boxes, cur_index,  next_index, box_memo):
    heightWithbox = 0
    if canbeabove(boxex, cur_index, next_index):
        if box_memo[next_index] ==0 :
            box_memo[next_index] = createStack(boxes, next_index, next_index+1, box_memo) + box_memo[next_index]
        heightwithbox = box_memo[next_index]
    heightwithoutbox = createStack(boxes, cur_index , next_index+1, box_memo )
    return max(heightwithbox, heightwithoutbox)