[SISS/C언어 스터디] 25-여름학기 3주차 스터디 - 동적 계획법

[SISS/C언어 스터디] 25-여름학기 3주차 스터디 - 동적 계획법

2학년 : Silver 5 이상, 3~4학년 : Silver 3 이상

자율 2문제를 풀어서 제출하면 됩니다.

백준 채점 확면 - 10844, 2156

 

10844

---

 

• 동적 계획법

#include <stdio.h>

#define MOD 1000000000
long long d[101][10]; // d[i][j]: i자리 수에서 마지막 자리가 j일 때의 경우의 수

int main() {
    int N;
    scanf("%d", &N);

    // 초기화: 한 자리 수는 1~9만 가능 (0은 제외)
    for (int i = 1; i <= 9; i++)
        d[1][i] = 1;

    // DP
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= 9; j++) {
            switch (j) {
                case 0:
                    // 끝자리가 0이면 이전 자리는 1만
                    d[i][j] = d[i - 1][1] % MOD;
                    break;
                case 9:
                    // 끝자리가 9면 이전 자리는 8만
                    d[i][j] = d[i - 1][8] % MOD;
                    break;
                default:
                    // 그 외에는 j-1, j+1
                    d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % MOD;
                    break;
            }
        }
    }

    // N자리 수 중 끝자리가 0~9인 경우의 수 합
    long long answer = 0;
    for (int i = 0; i <= 9; i++)
        answer = (answer + d[N][i]) % MOD;

    printf("%lld\n", answer);
    return 0;
}

 

2156

---

• 동적 계획법

#include <stdio.h>

#define MAX 10010

int arr[MAX], d[MAX]; // arr[i]: i번째 포도주 양, d[i]: i번째까지 마셨을 때 최대 양

// 세 수 중 최대값을 반환
int max3(int a, int b, int c) {
    if (a > b && a > c) return a;
    if (b > c) return b;
    return c;
}

int main() {
    int n;
    scanf("%d", &n);

    // 포도주 양
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }

    // 초기값
    d[1] = arr[1];
    if (n >= 2) d[2] = arr[1] + arr[2];

    // (점화식) DP
    for (int i = 3; i <= n; i++) {
        d[i] = max3(
            d[i - 3] + arr[i - 1] + arr[i], // i와 i-1을 마심 (i-2는 마시지 않음)
            d[i - 2] + arr[i],              // i만 마심
            d[i - 1]                        // i는 마시지 않음
        );
    }

    printf("%d\n", d[n]); // 최대 포도주 양
    return 0;
}