동적 계획법 (11) 썸네일형 리스트형 [ICPC] 백준 9341 - ZZ https://www.acmicpc.net/problem/9341 조건 정리 일단 문제를 편하게 풀기 위해 ZZ(0, 0)을 정의할 필요가 있다. $ZZ(0, 0) = b - a$로 둔다.(피보나치수열을 생각한다.) 직접 해보기 10 * 10 테이블을 단순한 dp로 출력해보자. 그러면 다음 발견을 할 수 있다. 어떤 항은 위처럼 Z 모양으로 더한 결과와 같다. 수식으로 나타내면 다음과 같다. $ZZ(a, b) = [\sum\limits_{i = 0}^{a}ZZ(i, b - 1)] + ZZ(0, b - 2)$ 그러면 우리는 위 식의 전개를 행렬로 표현할 수 있다. 예를 들어 c가 2인 경우 아래처럼 된다. $\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\.. 백준 1103 - 게임 https://www.acmicpc.net/problem/1103 이 포스트에서는 다소 무식한 방법을 사용한다. 일단 동적 계획법을 수행할 건데 테이블에서 상태는 "해당 위치를 갈 수 있는가?"로 정의하며 각 이동을 계산해 현재 테이블에서 다음 테이블로 바꾸는 방법을 사용할 것이다. 그러면 각 위치에서 상태가 1일 때(처음에는 (0, 0)만 1이다.) 주어진 조건에 따라갈 수 있는 좌표를 모두 1로 갱신하면 될 것이다. 물론 기존 테이블에다 갱신하는 게 아니라 다음에 쓸 테이블에다 해야 한다. 그러면 위치를 갱신하는 dp를 돌린다는 건 알겠는데 몇 번 하는가? 가 중요할 것이다. 어떤 특정한 횟수를 넘어서도 계속 이동할 수 있다면 게임을 무한으로 할 수 있다는 의미가 된다. 그러면 그 임계값을 정해야 하.. [KOI] 백준 2507 - 공주 구하기 https://www.acmicpc.net/problem/2507 발상 단순히 가는 경우면 어렵지 않게 계산할 수 있겠는데 구출하고 돌아와야 한다. 다음과 같은 생각을 해볼 수 있다. 갔다가 돌아오는 게 아니라 그냥 2명의 사람이 밟는 발판을 겹치지 않게 이동하기 이렇게 두면 테이블이 dp[501][501]인 dp 테이블을 구상할 수 있다. 위처럼 테이블을 두면 다음과 같은 점화식을 생각해볼 수 있다. f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로) 각각 i와 j에 대해 갈 수 있는 발판을 탐색하면서 경우의 수를 더하는 탑 다운 dp를 고려할 수 있다. 유의 사항 다만 이렇게 동적 계획법을 수행하면 주의해야 할 사항이 있다. 1. j는 목적지.. [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방향으로 좌표.. 백준 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의 수열의 개수를 관리할 것이다... 이전 1 2 3 다음
