DP (2) 썸네일형 리스트형 백준 1805번 나무수송 https://www.acmicpc.net/problem/1805 dp[i][j][k] 를 i번 노드를 루트로 하는 서브트리에 대해 목공소를 정확히 j개를 짓고 서브트리의 모든 나무가 i번 노드까지 이동했을때 k개의 나무가 목공소를 거치지 않은 경우의 최소 운반비 로 정할 수 있다.목공소의 여러 조합에 따른 k의 가짓수를 정확히 알수는 없지만 검은돌 트릭에 따라 노드를 합치는데 드는 비용이 생각보다 적기에 시간 안에 돌 수 있다는 계산으로 일단 코드를 짜 보았고 TLE를 받았다. #pragma GCC optimize("Ofast")#include using namespace std;int k;vector>> graph;vector w;vector>> dp;void dfs(int node){ dp[n.. 2021년 정올 본선 1번 헬기 착륙장 최대 반지름이 n인 원을 그리려면 페인트의 색깔과 관계없이 고정적으로 1부터 n까지의 합((n + 1)n / 2)만큼이 필요하다.따라서 dp[i][j] = 최대 반지름이 i인 원을 빨강 페인트 j통을 사용해서 색칠하는 경우의 수로 두었고 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i](가장 바깥 원을 어떤 색으로 칠할지를 나누어서) 가 나오게 된다. 이 DP를 전처리 해 두고 테스트 케이스에서 가능한 원의 크기마다 빨강 페인트의 사용 가능 범위인 max(0, 총 페인트량 - b)(파랑 페인트를 최대로 사용) 부터 a + 1(빨강 페인트를 최대로 사용) 이 나오니 이를 누적합으로 만들어서 해결하였다. 1시 57분 32초 제출, 64점#include #include #includ.. 이전 1 다음