백준 16493번 : 최대 페이지 수 (C 언어)

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

16493번: 최대 페이지 수

Code:

#include <stdio.h>
#define max(a,b) (a>b)?a:b
 
int n, m;
int dp[21][201] = { 0, };
int p[21] = { 0, };
int d[21] = { 0, };
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &p[i], &d[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (j - p[i] >= 0)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i]] + d[i]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d", dp[m][n]);
}

제공된 문제는 한양대학교 도서관에서 책을 빌려놓고 남은 기간 동안 최대한 많은 페이지를 읽어야 하는 상황을 다루고 있습니다. 각 챕터당 읽는데 소요되는 일 수와 페이지 수가 주어지고, 중요한 목표는 남은 기간 동안 읽을 수 있는 최대 페이지 수를 구하는 것입니다.

먼저, 제공된 코드의 알고리즘을 설명하겠습니다.

코드 설명:

1. n과 m을 입력받습니다. n은 남은 기간(일 수), m은 챕터의 수입니다.
2. 각 챕터당 읽는데 소요되는 일 수와 페이지 수를 배열에 저장합니다.
3. dp 배열을 사용하여 동적 프로그래밍을 수행합니다. dp[i][j]는 i번째 챕터까지 고려하고, j일 동안 읽었을 때 읽을 수 있는 최대 페이지 수를 나타냅니다.
4. 중첩된 두 개의 반복문을 사용하여 모든 챕터와 가능한 남은 기간에 대해 최대 페이지 수를 계산합니다.

해결 알고리즘:

1. 동적 프로그래밍 (Dynamic Programming):
   • dp[i][j]를 계산할 때, 이전 챕터의 최대 페이지 수(dp[i-1][j])와 현재 챕터를 읽고 남은 기간에 의해 얻을 수 있는 최대 페이지 수(dp[i-1][j-p[i]] + d[i])를 비교하여 최대값을 저장합니다.
2. 점화식:
   • dp[i][j] = max(dp[i-1][j], dp[i-1][j-p[i]] + d[i])
3. 최종 결과:
   • dp[m][n]이 최대 페이지 수를 나타냅니다.