bottom-up _ 최대증가수열(LIS)의 응용문제

김태원 t의 인프런 강의에서 나온 문제로 bottom-up 연습!

LIS를 응용하는 문제에요~ 라는 걸 알고 접근하니까 비교적 금방 풀 수 있었던 것 같다. 나중에 낯선 곳에서 이런 문제를 만나더라도, 아 너는 최대증가수열 풀던 방법처럼 bottom up으로 풀면 되겠구나! 라고 반갑게 알아볼 수 있으면 좋겠다..!!🤓

 

* 미약하게나마 .. 언제 이 LIS에서의 패턴을 적용할 수 있을지 감을 잡아놓자면.

지금으로서는, 직전 단계/범위 에서 고 바로 다음 단계/범위로 넘어가거나 확장할 때 규칙적으로 적용되는 논리나 패턴이 있는 듯하다면! (예를 들어 최대증가수열은 - 언제나 이전 수보다 추가할 수가 더 커야 한다든지, 이 문제의 경우 언제나 이전 벽돌보다 무게/밑면넓이가 더 커야 한다든지 하는!) 그 때 이런 bottom-up방식의 동적 계획법을 고려해보면 좋지 않을까 - 하는 정도로 기억해두려고 한다. 

점점 연습을 많이 해서 나중에는 더 명확하게 상황을 파악하고 특성을 잡아내서 접근방식을 떠올릴 수 있게 되길!ㅎㅎ

 

0. 문제

밑면이 정사각형인 직육면체 벽돌을 사용해 탑을 쌓는다. 조건을 만족하면서 쌓을 수 있는 최대 높이는 얼마일까?

 

(조건1) 벽돌은 회전 불가하다. 즉 옆면을 밑면으로 사용 X

(조건2) 모든 벽돌에 대해서 밑면의 넓이와 무게는 모두 다르다.

(조건3) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌을 쌓을 수 없다.

(조건4) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

1. 손계획

2. 코드

# 예시 자료
bricks = [
    [25, 3, 4],
    [4, 4, 6],
    [9, 2, 3],
    [16, 2, 5],
    [1, 5, 2]
]

# 무게 기준 내림차순 정렬하기
bricks.sort(key=lambda x: x[2], reverse=True)

# 각 벽돌에 대해, 자신이 꼭대기에 있을 경우 가능한 최대 높이를 기록할 배열 준비
max_h = [0] * len(bricks)

# 맨 앞에 있는 벽돌은 가장 무거운 친구라서, 자신이 꼭대기에 있을 경우 가능한 상황은, 자기 자신만 있는 경우이다.
# 그래서 가능한 최대 높이도 자신의 높이임을 미리 단정가능하다.
max_h[0] = bricks[0][1]

for i in range(1, len(bricks)):
    # 자신보다 밑면이 넓은 친구가 없을 경우, 디폴트 최대 높이는 자기 자신의 높이이므로 my_max 를 아래와 같이 초기화
    my_max = bricks[i][1]
    for j in range(0, i):
        if bricks[j][0] > bricks[i][0]:
            if my_max < max_h[j]+bricks[i][1]:
                my_max = max_h[j]+bricks[i][1]

    max_h[i] = my_max

print(f"쌓을 수 있는 최대 높이는 {max(max_h)} 입니다.")