백준 2655번 : 가장높은탑

https://www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

 

아이디어가 어렵진 않아서 풀 순 있었지만 재귀로 구현하는데 시간이 오래 걸렸던 문제다.

 

N개의 벽돌은 각각 높이와 서로 다른 넓이의 정사각형 밑면을 갖고 있고 무게도 모두 다르다. 이 벽돌들을 차례차례 쌓아올려서 가장 높은 탑을 만드려고 한다. 벽돌을 쌓기 위해서는 밑에 있는 블록보다 위에 있는 블록의 무게가 가벼워야하고, 밑면의 넓이도 작아야한다. 탑을 가장 높게 쌓아올렸을때 사용한 벽돌의 개수와 위부터 아래로 쌓은 벽돌의 번호를 순서대로 출력해야한다.

 

문제를 해결하기위한 아이디어로 완전탐색이 처음 떠올랐다. N개의 벽돌을 모두 검사하면서 현재 검사하는 벽돌 아래에 놓일 수 있는 벽돌이 있는지 확인하고, 있다면 그 벽돌을 아래에 놓고 다시 그 벽돌 아래에 놓을 수 있는 벽돌을 확인한다. 아래에 놓을 수 있는 벽돌이 여러개면 높이가 가장 커지는 벽돌을 선택한다. 

 

재귀적으로 함수를 호출하다보면 동일한 함수가 여러번 호출되는 부분이 생긴다. 예를 들어 1번 벽돌부터 순서대로 검사한다고 가정하면, 예시에서 3번 벽돌 아래에 놓을 수 있는 벽돌은 1번과 4번 벽돌이다. 그러니까 3번 벽돌 아래에는 1번과 4번 중 높이가 큰 벽돌을 놓아야한다. 그런데 앞서 1번 벽돌 아래에 놓인 벽돌들의 높이를 계산했었다. 즉, 1번 벽돌이 탑의 가장 위에 있을 때 만들어질 수 있는 가장 높은 탑의 높이를 계산했었다. 우리는 그 탑의 맨 위에 3번 블록만 얹어주면 된다. 따라서 d[i]에 저장되는 값은 i번째 블록이 탑의 가장 위에 있을 때 가능한 탑의 최고 높이와 그때의 사용한 블록 배열이다. 

 

import sys
input = sys.stdin.readline

def sol(i):

    if d[i][1] >= 0:
        return d[i][0], d[i][1]

    r, h = [], 0
    for j in range(1, n+1):
        if b[i][0] < b[j][0] and b[i][2] < b[j][2]:
            a, v = sol(j)
            if h < b[j][1] + v:
                r = [j] + a
                h = b[j][1] + v

    d[i][0] = r
    d[i][1] = h

    return r, h

n = int(input())
b = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[[], -1] for _ in range(n+1)]
v1, v2 = sol(0)
print(len(v1), *v1, sep='\n')