[Algorithm] 4주차 스터디 - 다이나믹 프로그래밍(백준 9095, 11726, 11048, 11568)

A - 백준 9095 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

* 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

* 코드

#include <iostream>

using namespace std;

int main(int argc, const char** argv) {
    int t;
    cin >> t;
    int dp[12] = { 0, 1, 2, 4 };

    for (int i=4; i<11; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }

    for (int i=0; i<t; i++) {
        int num;
        cin >> num;
        cout << dp[num] << endl;
    }

    return 0;
}

 

* 문제풀이

n=1 케이스부터 개수를 세어보면,

1, 2, 4, 7, 13, 24... 순으로 증가하는 걸 알 수 있다. n=4일 때부터 이전 연속 세 개의 원소를 더하면 해당 원소의 값이 나오는 수열이므로 n=k인 원소의 값은

dp[k] = dp[k-1] + dp[k-2] + dp[k-3]

이다.

 

B - 백준 11726번 2xn 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

* 문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

* 코드

#include <iostream>

using namespace std;

int main(int argc, const char** argv) {
    int n;
    int dp[1001] = { 0, 1, 2 };
    cin >> n;

    for (int i=3; i<=n; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007;
    }
    cout << dp[n] << endl;

    return 0;
}

 

* 문제풀이

2x1 직사각형을 아래 위로 쌓은 모양의 쌍을 몇 개 배치하냐에 따라 개수를 쉽게 셀 수 있다.

n=1인 케이스부터 차례대로 세어보면,

 

1, 2, 3, 5, 8, 13... 순으로 증가하는 수열이다. n=3일 때부터 이전 이전 연속 두 개의 원소를 더하면 해당 원소의 값이 나오는 수열이므로 n=k인 원소의 값은

dp[k] = dp[k-1] + dp[k-2]

이다.

 

C - 백준 11048번 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

* 문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

* 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int candy[1001][1001];
int dp[1001][1001] = { 0 };

int get_max(int a, int b, int c) {
    int result = max(a, b);
    result = max(result, c);
    return result;
}

int main(int argc, const char** argv) {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin >> candy[i][j];
        }
    }
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            dp[i][j] = candy[i][j] + get_max(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]);
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

* 문제 풀이

 현재 임의의 방의 위치를 (x, y)라고 했을 때 DP테이블(dp[x][y])은 (1,1)에서 출발해서 현재 방에 도착할 때까지 가질 수 있는 최대 사탕 개수로 정의한다.

 (r+1, c), (r, c+1), (r+1, c+1)로만 움직일 수 있기 때문에 (x,y)에 올 수 있는 방의 위치는 (x-1, y-1), (x, y-1), (x-1, y)이다. 이 세 개의 방까지 오면서 가져올 수 있는 각각의 최대 사탕 개수(dp[x-1][y-1], dp[x][y-1], dp[x-1][y-1]) 중에서 가장 큰 값을 뽑아 (x, y) 방의 사탕 개수와 더하면 (x, y)까지 가져올 수 있는 최대 사탕 개수가 되는 것이다. 따라서 (1, 1)에서부터 전체 방의 최대 사탕 개수를 구하면 최종 마지막 방인 (n, m)까지의 최대 사탕 개수를 구할 수 있다. 따라서 (r,c)까지의 최대 사탕개수를 구하는 식은

dp[r][c] = candy[r][c] + max(dp[r-1][c-1], dp[r-1][c], dp[r][c-1])

이다.

 

D - 백준 11568번 민균이의 계략

* 문제

민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 정해진 순서대로 보여줄 것이다. 준민이는 앞의 카드부터 임의의 개수만큼 골라서 민균이에게 제시하게 되는데, 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 예를 들어 민균이가 보여준 카드가 {4, 9, 10, 9} 일 때 준민이가 {4, 9}를 골랐다면 놀림을 받지 않겠지만, {4, 10, 9}이나 {9, 9}를 제시하면 놀림받게 될 것이다.

생각보다 바보가 아닌 준민이는 한번도 민균이에게 놀림을 받지 않았다. 이에 분노한 민균이는 하나의 조건을 더 추가했다. 이제 준민이가 제시해야하는 수열은 순증가여야 할 뿐만 아니라, 원소의 개수가 제일 많은 수열이여야 한다. 예를 들어 민균이가 보여준 카드가 {8, 9, 1, 2 ,10}일 때 준민이가 {8, 9, 10} 또는 {1, 2, 10}을 골랐다면 놀림을 받지 않겠지만, {8, 9}나 {1, 2}를 제시하면 놀림받게 될 것이다.

당황한 준민이는 일단 제시할 수 있는 수열의 원소의 최대 개수를 구해보기로 하였다. 예를 들어 {8, 9, 1, 2, 10}에서의 원소의 최대 개수는 3이 될 것이다. 도저히 못 풀겠어서 고민하던 준민이는 똑똑하기로 소문난 당신을 찾아가 이 문제를 의뢰하였다! 불쌍하고 딱한 준민이를 위해 이 문제를 해결하는 프로그램을 작성해보자.

* 코드

#include <iostream>

using namespace std;

int dp[1001];
int arr[1001];

int lis(int n){
    int i,j;
    int max = 1;
    for(i=1; i<=n; i++){
        dp[i] = 1;
        for(j=1; j<=i; j++){
            if(arr[j] < arr[i] && dp[j]+1 > dp[i]){
                dp[i] = dp[j]+1;
                if(max < dp[i])
                    max = dp[i];
            }
        }
    }
    return max;
}

int main(int argc, const char** argv) {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> arr[i];
    }

    cout << lis(n) << endl;
    return 0;
}

* 문제 풀이

원소가 증가하면서 길이가 최대인 부분 수열을 최장증가부분수열(Longest Increasing Subsequence Algorithm, LIS)이라고 한다. LIS의 길이를 알아내기 위해서 다이나믹 프로그래밍을 이용하고 DP 테이블(dp[index])은 index번 째 수를 마지막 원소로 가지는 부분수열의 길이로 정의된다. LIS의 길이를 구하기 위한 두 가지 조건은 다음과 같다.

1. arr[j] < arr[i]

증가 수열이어야 하므로 배열에서 현재 탐색하는 원소(arr[i])의 이전 원소들이 작은지 확인한다.

2. dp[j] + 1 > dp[i]

(j번째 원소를 마지막으로 갖는 부분수열의 길이) + 1 값(dp[j] + 1)이 이전에 탐색한 원소를 마지막으로 갖는 부분 수열의 길이(dp[i])보다 큰지 확인한다.

이 두 조건을 만족하면 arr[j]를 마지막으로 갖는 부분수열 arr[i]를 추가하면 지금까지 구했던 부분수열 중에 가장 큰 값을 가지게 된다.

이 두 조건을 만족하는 부분수열을 찾아 길이가 가장 긴 부분수열의 길이를 찾을 수 있다.