일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- boj
- ICPC 연습
- 기하
- 구현
- acmicpc.net
- IOI 2013
- BAPC 2018
- 세그먼트 트리
- 8192
- 백준 온라인 저지
- JOI
- DP
- Z 알고리즘
- convex hull
- 14179
- Z algorithm
- 그래프
- codeforces
- JOI 2018
- 컨벡스 헐
- POI Solution
- 2794
- Manacher's algorithm
- 코드포스
- 볼록 껍질
- Divide and conquer optimization
- Implementation
- 기하 알고리즘
- Manacher 알고리즘
- BAPC
- Today
- Total
프로그래밍 연습장
180428 동아리 연습 문제 풀이 본문
다음 점화식을 이용하여 문제를 해결한다.
$$dp(x) = min(dp(x-1), dp( {x \over 2} ), dp( {x \over 3} ) )$$
기저 조건은 $dp(1) = 0$이고, 계산할 때에 $dp( {x \over 2} )$와 $dp( {x \over 3} )$는 $x$가 각각 $2$와 $3$으로 나누어 떨어질 때에만 참조한다.
이는 아래의 소스 코드로 구현된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> #include <algorithm> using namespace std; int mem[1000004]; int f(int x) { if (x==1) return 0; if (mem[x] != 0) return mem[x]; int ans = f(x-1); if (x % 2 == 0) ans = min(ans, f(x/2)); if (x % 3 == 0) ans = min(ans, f(x/3)); ans += 1; mem[x] = ans; return ans; } int main() { int x; cin >> x; cout << f(x); } | cs |
피보나치 수를 구하는 것과 같다. 점화식은 다음과 같다.
$$f(x) = f(x-1) + f(x-2)$$
기저 조건은 $f(0) = f(1) = 1$이다.
가장 유명한 동적 계획법 문제 중 하나로, LIS(longest increasing subsequence)라고 불린다.
$dp(x)$를 부분수열 $a_{1..x}$에서의 문제의 답, 즉 그 안에서 가장 긴 증가하는 부분 수열의 길이로 정하자. 단, $dp(x)$에서는 $a_x$로 끝나는 부분 수열만 계산하기로 하자.(이는 동아리 시간에 말하는 걸 깜빡했다) 그러면 $x$ 이전의 다른 인덱스 $y$에 대해 $a_y < a_x$라면, $a_y$로 끝나는 부분수열에서 그대로 $a_x$를 가져다 붙이면 더 긴 증가 부분 수열을 구성할 수 있다. 따라서 점화식은 다음과 같다.
$$ dp(x) = max_{y<x, a_y < a_x} dp(y) + 1 $$
기저 조건 $dp(1) = 1$을 고려하여 계산하면, $dp$ 배열에 있는 모든 값의 합이 답이 된다. 시간 복잡도는 $O(n^2)$이다. 구글에 LIS를 검색하면 $O(n \log n)$ 솔루션이 존재하니, 관심 있는 사람들은 찾아보도록 하자.
$dp(x, y)$를, $x$번째 날까지 $y$개의 쿠폰을 남기고 여행하는 최소 비용으로 정의하자. 그러면 이제 문제의 규칙에 충실하게 점화식을 세우면 된다. 숫자가 커지니 천원 단위로 생각하자.
$dp(x, y) = dp(x-1, y)$ ($x$번째 날에 리조트를 이용할 수 없을 때)
$$dp(x, y) = \min ( dp(x-1, y) + 10, dp(x-3, y-1) + 25, dp(x-5, y-3) + 37, dp(x-1, y+3))$$
$y<0$인 경우는 아예 성립하지 않으므로 비용을 무한대(충분히 큰 수)로 처리해야 하고, 기저 조건은 $dp(0, 0) = 0$이다.
만약, 어떤 부분문자열이 팰린드롬인지 판별하는 함수 isPalin(i, j)가 구현되어 있다면, 다음과 같은 점화식으로 답을 구할 수 있을 것이다.
$dp(i, j)$를 $s[i..j]$를 나누는 최소 연산 수라고 정의할 때,
$$dp(i, j) = 1 + min_{i \le k < j, \operatorname{isPalin} (i, k)} dp(k+1, j) $$
이 때 isPalin 함수 또한 팰린드롬의 중심을 기반으로 양옆으로 뻗어나가면서 계산하는 동적 계획법으로 계산할 수 있다. 미리 전처리해 두어도 되고, dp2와 같은 새로운 함수를 구현해도 된다. isPalin의 점화식은 각자 생각해 보자.
$dp(i, j)$를 $i$번째 수까지 써서 수식의 결과값 $j$를 얻는 경우의 수로 정의하자. $(i, j)$ 상태에 도달할 수 있는 다음 두 가지 상태가 있다: $(i-1, j-a_i )$: $i$번째 수 직전에 "+"를 넣었을 때, $(i-1, j+a_i )$: $i$번째 수 직전에 "-"를 넣었을 때. 이 두 각각의 경우에 $j$가 $0$과 $20$ 사이에 들어오는지 체크하고, 올바른 값일 때에는 더해 주면 된다. 기저 조건은 $dp(0, 0) = 1$이다.
흔한 knapsack 문제(구글에 검색해 보자)와 비슷하게 생겼지만, 비용의 제한이 매우 작고 필요한 메모리가 매우 클 수 있다. 범위를 고려하여 다음과 같이 dp 배열을 정의해보자.
$dp(i, j) :=$ 현재 $i$번째 앱까지 고려하였을 때에 총 $j$ 이하의 비용을 사용했을 때에 확보할 수 있는 최대 메모리의 양
점화식과 코드는 생각보다 간단히 나올 것이다.
하나의 행만 있는 문제를 고려하자. 이 때의 점화식은 쉽게 생각할 수 있다: $f(i) = max(f(i-1), f(i-2) + a[i])$ 그러면, 각 행에 대해서 그 행 하나만 있는 문제의 답을 각각 그 점화식을 이용하여 구할 수 있을 것이다. 그 뒤, 다시 열의 관점에서 보면 똑같은 문제가 다시 나오는 것을 볼 수 있다.
이 또한 전형적인 dp 문제로(조금 복잡하지만), $dp(i, j)$를 $i$번째 날까지 $j$번의 강제 이주를 시켰을 때에 최소 소음으로 정의하게 된다. 열심히 풀어보자!! 모르겠으면 개인적으로 연락하자.
'문제 해결' 카테고리의 다른 글
190720 팀 연습: BAPC 2018 (2) | 2019.07.21 |
---|---|
180519 동아리 연습 문제 풀이 (0) | 2018.05.19 |
180421 동아리 연습 문제 풀이 (1) | 2018.04.21 |
180324 동아리 연습 문제 풀이 (0) | 2018.03.24 |
Polish Problems (11-15) (0) | 2018.03.14 |