2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 1. 분석 및 고찰 전에 포스팅했던 1272문제와 다른 tree dp문제를 경험했던 덕분에 각 노드가 루트가 되고 해당 노드의 상태가 0 혹은 1일때로 나누어 계산하면 된다는 점을 바로 깨달을 수 있었다. 2. 실패 이 문제는 추가적으로 back-tracking 과정을 걷혀야 하는데 이를 dp 업데이트 도중에 갱신하고자 하였으나 $N^2$의 공간 복잡도 문제로 고민하는 데 시간을 많이 소비하였다. 3. 성공 back-trackin..

출처 : https://www.acmicpc.net/problem/28220 28220번: 블록 쌓기 첫 번째 줄에 $N$, $L$, $R$이 공백으로 구분되어 주어진다. 두 번째 줄에 $A_1$, $\dots$, $A_N$이 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 설명 1~N번 칸이 존재하며 i번 칸에 {A_i}개의 블록이 쌓여있다. 각 칸에 쌓인 블록의 개수가 L이상 R이하가 되면서 {A_i}를 오름차순이 되도록 배치하고자 한다. 블록은 한 번에 양 옆으로 한 개씩만 옮길 수 있다. 블록을 옮기는 횟수의 최솟값을 구하라. 2. 실패 1 1) 접근 과정 이 문제를 처음 봤을 때 해당 조건을 만족하되 {A_i}가 최소이면 될 것이라고 간과하였다. 그래서 그리디로 접근해 보았다..