백준/DP (63) 썸네일형 리스트형 [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.. [KOI] 백준 2169 - 로봇 조종하기 https://www.acmicpc.net/problem/2169 힌트 1 더보기 주어진 상태 공간에서 방향을 반영한 DP 테이블을 설계할 수 있다. DP 테이블을 만들 수 있겠는가? 힌트 2 더보기 이 문제를 바텀 업 DP로 해결을 시도할 경우 $2MN$번 반복문을 돌아야 할 것이다. 혹시 자기의 코드가 $NM$번 반복문을 돌고 있을 경우 무엇을 빠트렸는지 생각해보자. 힌트 3 더보기 최장 경로를 찾아야 하면서도 입력 값에 음수가 들어간다. 혹시 DP 테이블 초기화에 문제가 있진 않는지 점검한다. 풀이 더보기 3방향으로 로봇이 움직이면서 최장 경로를 찾는 문제이다. $N, M \leq 1000$ 임을 감안하여 우리는 다음과 같은 DP 테이블을 생각할 수 있다. dp[i][j][k] := k방향으로 좌표.. 백준 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;.. 백준 17409 - 증가 수열의 개수 https://www.acmicpc.net/problem/17409 Intro 적당히 작은 N에 대해서는 DP[k][n] := n번째 수에서 LIS의 길이가 k인 경우의 수로 정의하여 $O(KN^{2})$ DP로 해결할 수 있다고 알려져 있다. 스택 오버플로우 다만 이 문제에서는 $N \leq 100000$ 이므로 무식하게 다중 반복문을 돌릴 수 없을 것이다. 어떻게 해야 할까? 아이디어 이 게시글 중반부에서 LIS를 세그먼트 트리로 구하는 법을 소개하고 있다. 이를 잘 응용하면 naive 한 DP를 수행하는데 걸리는 $O(N^{2})$ 시간 복잡도를 $O(N \log N)$으로 줄여볼 수 있지 않을까? 우리는 세그먼트 트리를 이용하여 n 이하의 수로 이루어지고 길이가 k의 수열의 개수를 관리할 것이다... 백준 18249 - 욱제가 풀어야 하는 문제 https://www.acmicpc.net/problem/18249 아이디어 문제에서 말한 그래프를 그려보자 문제의 요구사항에 맞춰 N개의 간선을 직접 선택하다 보면 다음 사실을 발견할 수 있다. 그래프를 위 그림처럼 보고 평행한 두 정점을 한 줄이라 취급했을 때 N개의 간선을 선택하면 N번째 줄까지 도달한 상태여야 한다. 즉 N개의 간선을 선택하는 방법은 N번째 줄에 도달하는 방법과 동치이며 한 줄을 잇는 한 줄 간선이나 4개의 정점을 교차하여 잇는 쌍칼 간선을 적절히 선택하여 N번째 줄에 도달하는 방법을 생각하면 된다. 쌍칼이 아니라 대각선 간선으로만 배치하는 경우 N개의 간선을 선택할 수 없다. 우리는 이 발견으로 다음 점화식을 세울 수 있다. $f(n) = f(n - 1) + f(n - 2) \;.. 이전 1 2 3 4 5 6 7 ··· 13 다음
