180428 동아리 연습 문제 풀이

A. 1로 만들기

다음 점화식을 이용하여 문제를 해결한다.

$$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$으로 나누어 떨어질 때에만 참조한다.

이는 아래의 소스 코드로 구현된다.

#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);
}

B. 2×n 타일링

피보나치 수를 구하는 것과 같다. 점화식은 다음과 같다.

$$f(x) = f(x-1) + f(x-2)$$

기저 조건은 $f(0) = f(1) = 1$이다.

C. 가장 긴 증가하는 부분 수열

가장 유명한 동적 계획법 문제 중 하나로, 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)$ 솔루션이 존재하니, 관심 있는 사람들은 찾아보도록 하자.

D. 리조트

$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$이다. 

E. 팰린드롬 분할

만약, 어떤 부분문자열이 팰린드롬인지 판별하는 함수 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의 점화식은 각자 생각해 보자.

F. 1학년

$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$이다.

G. 앱

흔한 knapsack 문제(구글에 검색해 보자)와 비슷하게 생겼지만, 비용의 제한이 매우 작고 필요한 메모리가 매우 클 수 있다. 범위를 고려하여 다음과 같이 dp 배열을 정의해보자.

$dp(i, j) :=$ 현재 $i$번째 앱까지 고려하였을 때에 총 $j$ 이하의 비용을 사용했을 때에 확보할 수 있는 최대 메모리의 양

점화식과 코드는 생각보다 간단히 나올 것이다.

H. 사탕 줍기 대회

하나의 행만 있는 문제를 고려하자. 이 때의 점화식은 쉽게 생각할 수 있다: $f(i) = max(f(i-1), f(i-2) + a[i])$ 그러면, 각 행에 대해서 그 행 하나만 있는 문제의 답을 각각 그 점화식을 이용하여 구할 수 있을 것이다. 그 뒤, 다시 열의 관점에서 보면 똑같은 문제가 다시 나오는 것을 볼 수 있다.

I. ZAVABA

이 또한 전형적인 dp 문제로(조금 복잡하지만), $dp(i, j)$를 $i$번째 날까지 $j$번의 강제 이주를 시켰을 때에 최소 소음으로 정의하게 된다. 열심히 풀어보자!! 모르겠으면 개인적으로 연락하자.