dp[i]) { //모든 상자에 대해 그 앞 상자 검사 dp[i] = dp[j] + 1; //갱신 } } if (dp[i] > max) max = dp[i]; } printf("%d\n", max); return 0; }"> dp[i]) { //모든 상자에 대해 그 앞 상자 검사 dp[i] = dp[j] + 1; //갱신 } } if (dp[i] > max) max = dp[i]; } printf("%d\n", max); return 0; }"> dp[i]) { //모든 상자에 대해 그 앞 상자 검사 dp[i] = dp[j] + 1; //갱신 } } if (dp[i] > max) max = dp[i]; } printf("%d\n", max); return 0; }">

<aside> 1️⃣

문제: 1965번 상자넣기

정육면체 상자가 일렬로 있을 때, 앞의 상자가 뒤의 상자보다 작으면 앞의 상자를 뒤의 상자 안에 넣을 수 있음

한번에 넣을 수 있는 최대 상자개수 구하기

</aside>

#include <stdio.h>

//dp로 구현
int main() {
    int n;
    int box[1001]; //상자 크기 저장 배열
    int dp[1001]; //i번째 상자를 마지막으로 하는 최대 상자 개수
    int max = 0;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &box[i]);
    }

    for (int i = 0; i < n; i++) {
        dp[i] = 1; //자기 자신만 선택했을 경우 최소 1
        for (int j = 0; j < i; j++) {
            //j번 상자를 i번째에 넣을 수 있는 경우
            if (box[j] < box[i] && dp[j] + 1 > dp[i]) { //모든 상자에 대해 그 앞 상자 검사
                dp[i] = dp[j] + 1; //갱신
            }
        }
        if (dp[i] > max) max = dp[i];
    }

    printf("%d\\n", max);
    return 0;
}

image.png

<aside> 2️⃣

문제: 2004번 조합 0의 개수

$n \choose m$의 끝자리 0의 개수를 출력

#include <stdio.h>

long long count_factor(long long n, int factor) {
    long long count = 0;
    while (n >= factor) {
        count += n / factor;
        n /= factor;
    }
    return count;
}

int main() {
    long long n, m;
    scanf("%lld %lld", &n, &m);

    //끝자리 0의 개수는 2와 5의 짝의 개수로 정해짐
    //count_2 = f2(n) - f2(m) - f2(n-m)
    //count_5 = f5(n) - f5(m) - f5(n-m)
    long long twos = count_factor(n, 2) - count_factor(m, 2) - count_factor(n - m, 2);
    long long fives = count_factor(n, 5) - count_factor(m, 5) - count_factor(n - m, 5);

    long long result = (twos < fives) ? twos : fives;
    printf("%lld\\n", result);
    return 0;
}

image.png