백준 2655번 가장 높은 탑 쌓기

백준 2655번 - 가장 높은 탑 쌓기 가장 높은 탑 쌓기 문제의 경우 전형적인 dp문제 중 하나이다. 조건 중 하나가 밑의 블럭의 크기와 무게가 현재 블럭 보다 더 커야 한다는 조건이 있다. 이전의 위치한 블럭의 값 들과 계속해서 비교하면서 값을 업데이트해준다. 우선 시작하기전에 필자의 경우에는 넓이의 기준으로 내림차순으로 정렬했다. (물론 무게를 기준으로 정렬해도 된다.) 그래서 블럭의 이전의 값들과 비교하기 편하다. 내림차순이면 이전의 넓이는 항상 큰 값이 된다. 따라서 점화식은 아래와 같다. dp[i] i번째 블럭의 가장 높은 높이이다. if(올릴 수 있는 블럭이라면) { // 현재 블럭이 더 가볍고 부피가 작다면 dp[now] = max(dp[now], dp[prev] + height[now])..

2021.01.20