프로그래밍 연습장

180428 동아리 연습 문제 풀이 본문

문제 해결

180428 동아리 연습 문제 풀이

김준원 2018. 4. 28. 17:31

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


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


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==1return 0;
    if (mem[x] != 0return 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


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$번의 강제 이주를 시켰을 때에 최소 소음으로 정의하게 된다. 열심히 풀어보자!! 모르겠으면 개인적으로 연락하자.

'문제 해결' 카테고리의 다른 글

190720 팀 연습: BAPC 2018  (2) 2019.07.21
180519 동아리 연습 문제 풀이  (0) 2018.05.19
180428 동아리 연습 문제 풀이  (1) 2018.04.28
180421 동아리 연습 문제 풀이  (1) 2018.04.21
180324 동아리 연습 문제 풀이  (0) 2018.03.24
Polish Problems (11-15)  (0) 2018.03.14
1 Comments
댓글쓰기 폼