DP (37) 썸네일형 리스트형 백준 1937 - 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다음 dp 테이블을 세운다. dp[i][j] := 좌표 (i, j)에서 시작했을 때 가질 수 있는 최장 경로의 길이 각 좌표마다 가질 수 있는 최장 경로를 DFS로 검색하면 $O(V^{2}E)$가 되어 시간 초과를 받게 된다. 이를 $O(V^{2})$로 줄여보자. 각 정점마다 DFS를 수행하면서 거쳐간 정점에 저장한 지역 최장 경로는 일단 저장한다. 그리고 이미 거쳐간 정점에 대해서는 .. [ICPC] 백준 11066 - 파일 합치기 https://www.acmicpc.net/problem/11066 다음 DP 테이블을 세운다. dp[i][j] := i번째부터 j번째 파일까지 합치는 최소 비용 4중 반복문으로 i번째 책을 시작으로 j + 1개의 연속된 책을 합치려고 하는데 pivot이 m번째 책일 때 양 옆의 책들을 합치는 비용을 계산하면서 테이블을 채우는 방법을 생각할 수 있다. 다만 연속된 책을 합치는 과정을 반복문마다 수행하면 시간 초과를 받을 위험이 있다. 누적합으로 파일을 합치는 비용을 미리 계산하면 일부 연속된 책을 합치는 비용을 $O(1)$의 시간 복잡도로 처리할 수 있으므로 3중 반복문으로 줄어든다. 주어지는 TC에 대해 3중 반복문으로 테이블을 채운 후 최소 비용을 출력하면 정답을 받을 수 있다. 전체 코드 더보기 #.. [KOI] 백준 2616 - 소형기관차 https://www.acmicpc.net/problem/2616 다음 dp 테이블을 생각한다. dp[i][j] := j번째 객차까지 소형 기관차 i개를 썼을 때 수송할 수 있는 최댓값 이렇게 했을 때 지금 객차부터 소형 기관차를 하나 사용하여 사람들을 수송했을 때, 지금 객차에서 소형 기관차를 사용하지 않고 다음 객차로 넘어갔을 때를 메모이제이션하여 문제를 풀 수 있다. 일일이 객차의 인원을 더하는 것은 무리이므로 객차별 인원을 누적합으로 관리하면 제한 시간 내에 정답을 받을 수 있다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include u.. Rerooting Technique on Tree 이 게시글에서는 트리에서 할 수 있는 rerooting technique라는 것을 다뤄본다. Rerooting? 자연수 N개의 노드로 구성되고 루트가 정해진 트리가 주어져 있고 배열에 다음과 같은 정보가 담기길 원한다고 해보자. sub[i] = i번째 노드가 루트인 서브 트리에 대해 해당 트리에 속한 노드의 개수 이 배열을 완성하기 위해서 어떻게 해야 할까? 먼저 생각나는 단순한 방법으로는 각 노드마다 dfs를 돌아 노드의 개수를 세는 $O(N^{2})$ 방법을 떠올릴 수 있다. 하지만 당연하게도 이런 글을 쓴다는 것은 $O(N^{2})$ 시간 복잡도로 해결할 수 없도록 N의 크기가 $10^{5}$ 이상인 경우에 대해 푸는 방법을 알아보는 것이므로 위 방법은 쓸 수 없다. 게다가 각 노드가 루트라고 할 .. 백준 13555 - 증가하는 부분 수열 https://www.acmicpc.net/problem/13555 17409 - 증가 수열의 개수와 풀이가 같다. 다만 17409와 달리 원소의 상한과 수열의 길이가 불일치라는 것과 세그먼트 트리가 아닌 펜윅 트리로만 풀린다는 점을 유의하여 구현하도록 한다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; #define mod 5000000 int n, k; int dp[51][100001]; int sum(int pos, int seq) { if (!seq) return 1; int ret = 0;.. 이전 1 2 3 4 ··· 8 다음
