다이나믹 프로그래밍 여러가지 점화식으로 풀어보기

1563번 문제: 개근상 문제를 여러가지 점화식으로 풀어봅시다.

출결사항은 출석, 지각, 결석으로 총 3가지가 있습니다.

개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람입니다.

한 학기가 4일인 경우에 O를 출석, L을 지각, A를 결석으로 나타내보면, 개근상을 받을 수 있는 출결 정보는 아래와 같이 43가지입니다.

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

한 학기가 N일인 경우에 개근상을 받을 수 있는 출결 정보의 개수는 총 몇 개 일까요?

방법 1

  • D[Day][Now][Prev][Prev2][Late] = Day일, 지금 상태가 Now이고, 전날 상태가 Prev, 전전날 상태가 Prev2이고, 지각이 Late 번 했을 때 가능한 출결 정보의 개수 (상태 : 출석(0), 결석(1), 지각(2))

먼저, 이 점화식은 3일의 정보가 포함되어 있기 때문에, Day=3인 경우의 초기값을 모두 채워줘야 합니다.

  • D[3][Now][Prev][Prev2][1] = 1 (Now ==2 || Prev == 2 || Prev2 == 2)
    • 지각(2)을 1번이라도 했기 때문에, 마지막 Late에는 1일 들어가야 함
  • D[3][Now][Prev][Prev2][0] = 1

그림 경우의 수를 나눠봅시다.

  1. 오늘 출석을 했을 때
  2. 오늘 결석을 했을 때
  3. 오늘 지각을 했을 때

총 3가지가 있습니다.

오늘 출석을 했고 (Now = 0), 전날은 Prev, 전전날은 Prev2를 한 경우를 생각해봅시다.

이 것은 D[Day][0][Prev][Prev2]와 같습니다. 그럼 Day-1날에는 D[Day-1][Prev][Prev2][Prev3]을 했을 것입니다.

따라서, 오늘 출석을 했고, 지금까지 지각을 0번 했다면, D[Day][0][Prev][Prev2][0] += D[Day-1][Prev][Prev2][Prev3][0] 일 것이고

오늘 출석을 했는데, 지금까지 지각을 1번 했다면, D[Day][0][Prev][Prev2][1] += D[Day-1][Prev][Prev2][Prev3][1] 이 될 것입니다.

오늘 결석을 한 경우도 출석과 비슷하게 생각할 수 있기 때문에, 지각을 0번 했다면 D[Day][1][Prev][Prev2][0] += D[Day-1][Prev][Prev2][Prev3][0], 1번 했다면 D[Day][1][Prev][Prev2][1] += D[Day-1][Prev][Prev2][Prev3][1] 일 될 것입니다. 여기서 결석은 3일 연속으로 할 수 없기 때문에, Prev == 1 && Prev2 == 1인 경우는 빼주고 채워야 합니다.

오늘 지각을 했다면, 지금까지는 지각을 한 번도 하지 않았어야 합니다. 따라서, D[Day][2][Prev][Prev2][1] += D[Day-1][Prev][Prev2][Prev3][0] 이 됩니다.

정답은 D[Day][i][j][k][l]에 들어있는 값을 모두 더해주면 됩니다. (Day = N, 0 ≤ i, j, k ≤ 2, 0 ≤ l ≤ 1)

이 방법을 코드로 작성해보면 다음과 같습니다.

#include <iostream>
#include <cstdio>
using namespace std;
int mod = 1000000;
int d[1001][3][3][3][2];
// 출석: 0, 결석: 1, 지각: 2
int main() {
    int n;
    cin >> n;
    for (int now=0; now<3; now++) {
        for (int prev=0; prev<3; prev++) {
            for (int prev2=0; prev2<3; prev2++) {
                if (now == prev && prev == prev2 && prev2 == 1) {
                    // 결석 연속 3번
                    continue;
                }
                if ((now == 2 && prev == 2) ||
                        (now == 2 && prev2 == 2) ||
                        (prev == 2 && prev2 == 2)) {
                    // 지각 1번
                    continue;
                }
                if (now == 2 || prev == 2 || prev2 == 2) {
                    d[3][now][prev][prev2][1] = 1;
                } else {
                    d[3][now][prev][prev2][0] = 1;
                }
            }
        }
    }
    for (int i=4; i<=n; i++) {
        for (int prev=0; prev<3; prev++) {
            for (int prev2=0; prev2<3; prev2++) {
                for (int prev3=0; prev3<3; prev3++) {
                    // 출석
                    d[i][0][prev][prev2][0] += d[i-1][prev][prev2][prev3][0];
                    d[i][0][prev][prev2][0] %= mod;
                    d[i][0][prev][prev2][1] += d[i-1][prev][prev2][prev3][1];
                    d[i][0][prev][prev2][1] %= mod;
                    // 결석
                    if (prev == 1 && prev2 == 1) {
                        // 결석 3번은 불가능
                    } else {
                        d[i][1][prev][prev2][0] += d[i-1][prev][prev2][prev3][0];
                        d[i][1][prev][prev2][0] %= mod;
                        d[i][1][prev][prev2][1] += d[i-1][prev][prev2][prev3][1];
                        d[i][1][prev][prev2][1] %= mod;
                    }
                    // 지각
                    d[i][2][prev][prev2][1] += d[i][prev][prev2][prev3][0];
                    d[i][2][prev][prev2][1] %= mod;
                }
            }
        }
    }
    if (n == 0) {
        printf("0\n");
    } else if (n == 1) {
        printf("3\n");
    } else if (n == 2) {
        printf("8\n");
    } else {
        int ans = 0;
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                for (int k=0; k<3; k++) {
                    for (int l=0; l<2; l++) {
                        ans += d[n][i][j][k][l];
                        ans %= mod;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

방법 2

점화식을 방법 1과 조금 다르게 새워볼 수 있습니다.

  • D[Day][i][j][k] = 수업이 총 Day개이고, 결석을 연속으로 i번, 지각을 j번, Day날의 출결정보(k)가 출석(0), 결석(1), 지각(2) 일 때, 출결정보의 경우의 수

첫 날 가능한 경우는 아래와 같이 3가지 입니다.

  1. 출석을 한 경우: D[1][0][0][0] = 1
  2. 결석을 한 경우: D[1][1][0][1] = 1
  3. 지각을 한 경우: D[1][0][1][2] = 1

오늘 출석을 했다면, 결석은 연속으로 0번 한 것입니다. 따라서, i = 0이 됩니다. 이제, 지각을 1번한 경우와 0번한 경우로 나눌 수 있습니다.

  1. 지각을 0번 했을 때는, 전날 할 수 있는 출결 정보는 출석과 결석밖에 없습니다.
    • D[i][0][0][0] = D[i-1][0][0][0] + D[i-1][1][0][1] + D[i-1][2][0][1]
  2. 지각을 1번 한 경우는, 전날 할 수 있는 출결 정보가 출석, 결석, 지각 입니다.
    • D[i][0][1][0] = D[i-1][0][1][0] + D[i-1][1][1][1] + D[i-1][2][1][1] + D[i-1][0][1][2]

오늘 결석을 했다면, 첫 번째 결석과 두 번째 연속 결석으로 나눌 수 있습니다. 그리고, 각각의 경우에서 지각의 횟수를 1과 0으로 나눌 수 있습니다.

  1. 오늘이 첫 번째 결석이고, 지각을 한 번도 한 적이 없으면, 전날은 반드시 출석이어야 한다
    • D[i][1][0][1] = D[i-1][0][0][0]
  2. 오늘이 두 번째 결석이고, 지각을 한 번도 한 적이 없다면, 전날은 반드시 결석이어야 한다
    • D[i][2][0][1] = D[i-1][1][0][1]
  3. 오늘이 첫 번째 결석이고, 지각을 한 번 한 적이 있으면, 전날은 반드시 출석이거나 지각이다
    • D[i][1][1][1] = D[i-1][0][1][0] + D[i-1][0][1][2]
  4. 오늘이 두 번째 결석이고, 지각을 한 번 한적이 있어도, 전날은 반드시 결석이다
    • D[i][2][1][1] = D[i-1][1][1][1]

오늘 지각을 했다면, 전날 까지 지각은 있으면 안되고, 출석이나 결석이어야 합니다.

따라서, D[i][0][1][2] = D[i-1][0][0][0] + D[i-1][1][0][1] + D[i-1][2][0][1] 이 됩니다.

정답은 D[Day][i][j][k]에 들어있는 모든 값을 더하면 됩니다. (Day = N, 0 ≤ i, k ≤ 2, 0 ≤ j ≤ 1)

#include <iostream>
#include <cstdio>
using namespace std;
int mod = 1000000;
int d[1001][3][2][3];
// 출석: 0, 결석: 1, 지각: 2
int main() {
    int n;
    cin >> n;
    d[1][0][0][0] = 1;
    d[1][1][0][1] = 1;
    d[1][0][1][2] = 1;
    for (int i=2; i<=n; i++) {
        d[i][0][0][0] = d[i-1][0][0][0] + d[i-1][1][0][1] + d[i-1][2][0][1];
        d[i][0][1][0] = d[i-1][0][1][0] + d[i-1][1][1][1] + d[i-1][2][1][1] + d[i-1][0][1][2];
        d[i][1][0][1] = d[i-1][0][0][0];
        d[i][2][0][1] = d[i-1][1][0][1];
        d[i][1][1][1] = d[i-1][0][1][0] + d[i-1][0][1][2];
        d[i][2][1][1] = d[i-1][1][1][1];
        d[i][0][1][2] = d[i-1][0][0][0] + d[i-1][1][0][1] + d[i-1][2][0][1];
        for (int j=0; j<3; j++) {
            for (int k=0; k<2; k++) {
                for (int l=0; l<3; l++) {
                    d[i][j][k][l] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i=0; i<3; i++) {
        for (int j=0; j<2; j++) {
            for (int k=0; k<3; k++) {
                ans += d[n][i][j][k];
                ans %= mod;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

방법 3

  • D[Day][Late][Prev][Now] = Day일에 지각은 Late번, 전날 상태: Prev, 오늘 상태: Now (출석: 0, 지각: 1, 결석: 2)

초기화는 다음과 같이 할 수 있습니다.

  • D[2][i%2+j%2][i][j] = 1

여기서 i%2 + j%2는 지각의 횟수를 나타내며, i%2 + j%2는 항상 1보다 작거나 같아야 합니다.

전전날에 한 출결 정보가 Prev2 라면, 아래와 같은 식으로 나타낼 수 있습니다.

  • D[Day][Late+Now%2][Prev][Now] += D[Day-1][Late][Prev2][Prev]
    • 0 ≤ Prev, Now, Prev2 ≤ 2
    • 0 ≤ Late + Now%2 ≤ 1

지각을 1로 나타냈기 때문에, %2를 이용해서 지각인지 아닌지를 판별 할 수 있습니다.

결석이 연속으로 3번인지에 대한 처리는 Now + Prev + Prev2 == 6으로 할 수 있습니다.

정답은 D[Day][Late][Prev][Now] 에 저장되어 있는 값을 모두 더하면 됩니다. (Day = N, 0 ≤ Late ≤ 1, 0 ≤ Prev, Now ≤ 2)

#include <iostream>
#include <cstdio>
using namespace std;
int mod = 1000000;
int d[1001][2][3][3];
int main() {
    int n;
    cin >> n;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            if (i%2 + j%2 == 2) continue;
            d[2][i%2+j%2][i][j] = 1;
        }
    }
    for (int i=3; i<=n; i++) {
        for (int prev=0; prev<3; prev++) {
            for (int now=0; now<3; now++) {
                for (int late=0; late+now%2<=1; late++) {
                    for (int prev2=0; prev2<3; prev2++) {
                        if (prev+now+prev2 == 6) continue;
                        d[i][late+now%2][prev][now] += d[i-1][late][prev2][prev];
                        d[i][late+now%2][prev][now] %= mod;
                    }
                }
            }
        }
    }
    if (n == 1) {
        printf("3\n");
    } else {
        int ans = 0;
        for (int i=0; i<=1; i++) {
            for (int j=0; j<3; j++) {
                for (int k=0; k<3; k++) {
                    ans += d[n][i][j][k];
                    ans %= mod;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

방법 4

  • D[i][j][k] = i일, 지각 j번, 연속 결석 k번

    • k = 0: 출석 또는 지각
    • k = 1, 2: 결석 (연속 결석 1번 또는 2번)
  • 초기값: D[0][0][0] = 1

오늘 출석을 했으면, 전날에 출석, 지각, 결석 중에 하나만 하면 됩니다. D[i][j][0] += D[i-1][j][k] (0 ≤ k ≤ 2)

오늘 지각을 하려면 j 가 1이어야 합니다. D[i][1][0] += d[i-1][0][k]

오늘 결석을 하려면 k < 2이어야 합니다. D[i][j][k+1] += D[i-1][j][k]

정답은 D[i][j][k]에 저장되어 있는 값을 모두 더하면 됩니다. (i = N, 0 ≤ j ≤ 1, 0 ≤ k ≤ 2)

#include <iostream>
#include <cstdio>
using namespace std;
int mod = 1000000;
int d[1001][2][3];
int main() {
    int n;
    cin >> n;
    d[0][0][0] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<2; j++) {
            for (int k=0; k<3; k++) {
                d[i][j][0] += d[i-1][j][k];
                d[i][j][0] %= mod;
                if (j == 0) {
                    d[i][1][0] += d[i-1][j][k];
                    d[i][1][0] %= mod;
                }
                if (k < 2) {
                    d[i][j][k+1] += d[i-1][j][k];
                    d[i][j][k+1] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i=0; i<2; i++) {
        for (int j=0; j<3; j++) {
            ans += d[n][i][j];
            ans %= mod;
        }
    }
    cout << ans << '\n';
    return 0;
}

방법 5

방법 5는 지각이 없다고 가정하고 문제를 풉니다.

  • D[i][j] = i일, 연속 결석이 j번
    • j = 0이면 출석
    • j = 1, 2 이면 결석

오늘 출석을 하는 경우에는 전날 아무거나 해도 상관이 없습니다. D[i][0] += D[i-1][j] (0 ≤ j ≤ 2)

오늘 첫 결석을 하는 경우라면, 전날은 반드시 출석을 해야 합니다. D[i][1] = D[i-1][0]

오늘 한 결석이 연속 결석의 두번째 날이라면, 전날은 반드시 첫 결석이어야 합니다. D[i][2] = D[i-1][1]

정답은 D[n][0] + D[n][1] + D[n][2]가 됩니다.

그런데, 지각을 한 번 할 수 있습니다.

지각을 k일에 했다면, 출결 정보는 k를 기준으로 좌우로 나누어지게 됩니다.

k일의 왼쪽은 총 k-1일, 오른쪽은 총 N-k일 입니다.

지각을 k일에 한 경우, 출결 정보의 개수는 D[i-1][i] * D[N-k][j] (0 ≤ i, j ≤ 2)가 됩니다.

#include <iostream>
#include <cstdio>
using namespace std;
int mod = 1000000;
int d[1001][3];
int main() {
    int n;
    cin >> n;
    d[0][0] = 1;
    for (int i=1; i<=n; i++) {
        d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2];
        d[i][1] = d[i-1][0];
        d[i][2] = d[i-1][1];
        for (int j=0; j<3; j++) {
            d[i][j] %= mod;
        }
    }
    int ans = 0;
    for (int i=0; i<3; i++) {
        ans += d[n][i];
        ans %= mod;
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<3; j++) {
            for (int k=0; k<3; k++) {
                long long temp = (long long)d[i-1][j] * d[n-i][k];
                ans += temp % mod;
                ans %= mod;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

댓글 (3개) 댓글 쓰기


hbh1107 7년 전

안녕하세요

다름이 아니라 아래 문제 다이나믹 프로그래밍 두문제를 풀다 막혀서 몇주 고민하다하다 조언을 구하고자 글 남깁니다.

https://www.acmicpc.net/problem/1514 <= 풀이 방법 DP. 최대 3개의 디스크까지 동시 회전이 가능하므로 DP[c][n1][n2] : c는 현재 확인해야 될 디스크 위치. n1은 현재 디스크의 숫자. n2는 다음 디스크의 숫자. 로 DP를 구현했습니다.

https://www.acmicpc.net/problem/2394 <= 기본적으로 KOI 2008 공주구하기와 유사한 방법으로 접근하였습니다. DP[a][b] N으로 가는 위치가 a이고 N에서 1로 다시 오는 위치가 b에 있을때의 경우의 수중 방문하는 node가 가장 많은 경우를 return하게 했습니다. 그런데 어느 부분이 잘못된 것인지 막막한 상태라 조언을 구하게 되었습니다.

알려주시면 감사하겠습니다.

include

define INF 0x7fffff

define MAXN 260

int N; int idx1, idx2; int path1[MAXN]; int path2[MAXN]; int map[MAXN][MAXN]; int memo[MAXN][MAXN];

int max(int a, int b) { if (a > b) return a; else return b; }

int calc(int a, int b, int k) { int ret;

if (k == N) {
    if (map[a][N] && map[b][N])
        return memo[a][b] = 1;
    else
        return -INF;
}

if (memo[a][b] != -1)
    return memo[a][b];

memo[a][b] = calc(a, b, k + 1);
if (map[a][k]) {
    ret = calc(k, b, k + 1) + 1;
    memo[a][b] = max(ret, memo[a][b]);      
}

if (map[b][k]) {
    ret = calc(a, k, k + 1) + 1;
    memo[a][b] = max(ret, memo[a][b]);
}

return memo[a][b];

}

void init() { int i, j; idx1 = idx2 = 0; for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) memo[i][j] = -1, map[i][j] = 0; path1[0] = 1; path2[0] = 1; path1[++idx1] = N; }

void find_path(int a, int b) { int i, mx_a, mx_b, nexta, nextb;

if (a == N || b == N)
    return;

mx_a = -INF; mx_b = -INF;
for (i = a + 1; i <= N; i++) {
    if (map[a][i] && i != b && memo[i][b] > mx_a) {
        mx_a = memo[i][b];
        nexta = i;
    }
}

for (i = b + 1; i <= N; i++) {
    if (map[b][i] && i != a && memo[a][i] > mx_b) {
        mx_b = memo[a][i];
        nextb = i;
    }
}

if (mx_a > 0 || mx_b > 0) {
    if (mx_a > mx_b) {
        path1[++idx1] = nexta;
        find_path(nexta, b);
    }
    else {
        path2[++idx2] = nextb;
        find_path(a, nextb);
    }
}

}

void swap(int a, int b) { int temp; temp = a; a = b; b = temp; }

void sort() { int i, j; for (i = 0; i < idx1; i++) for (j = i + 1; j <= idx1; j++) { if (path1[i] > path1[j]) swap(&path1[i], &path1[j]); } for (i = 0; i < idx2; i++) for (j = i + 1; j <= idx2; j++) { if (path2[i] < path2[j]) swap(&path2[i], &path2[j]); } }

void print_memo() { int i, j; for (i = 1; i <= N; i++) { for (j = 1; j <= N; j++) { printf("%13d", memo[i][j]); } printf("\n"); } }

int main() { int i, j, ret, p, q, mx, tmp_idx;

freopen("sample_input.txt", "r", stdin);
freopen("sample_output.txt", "w", stdout);

scanf("%d", &N);
init();
do {
    scanf(" %d %d", &p, &q);
    map[p][q] = 1;
    map[q][p] = 1;
} while (p && q);

ret = calc(1, 1, 2);    

//print_memo();
if (ret <= 0) {
    printf("0\n");
}
else if (ret == 1) {
    printf("2\n1 %d 1\n", N);
}
else {
    find_path(1, 1);
    printf("%d\n", ret + 1);
    sort();
    for (i = 0; i <= idx1; i++)
        printf("%d ", path1[i]);
    for (i = 0; i <= idx2; i++)
        printf("%d ", path2[i]);
    printf("\n");
}
//printf("%d %d\n", idx1, idx2);
return 0;

}


baekjoon 7년 전

안녕하세요.

질문은 게시판을 이용해 주세요.


sgchoi5 7년 전

방법 1 에 있는 주석이 오타가 아닌지요?

// 지각 1번

코드 의미로는 지각 2번으로 고쳐야 할 것 같습니다.