백준 29704번 : 벼락치기 (C 언어)

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

29704번: 벼락치기

Code:

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

문제 설명:

주어진 문제는 혜민이가 숙명여자대학교의 알고리즘 학회 ALGOS에 합격했지만, 과제 기한 내에 프로그래밍 문제를 해결하지 못할 경우 내야 하는 벌금을 최소화하는 문제입니다. 주어진 입력으로는 문제의 개수 N과 남은 제출 기한 T가 주어지며, 각 문제를 풀 때 걸리는 일수와 해당 문제의 벌금 정보도 주어집니다.

프로그래밍 과제를 해결하는 데 필요한 일수와 벌금 정보를 이용하여, 가능한 한 적은 벌금을 내도록 혜민이가 문제를 풀어야 합니다.

코드 설명:

 

1. 문제 개수 N과 제출 기한 T을 입력 받습니다.
2. 각 문제의 걸리는 일수와 벌금을 입력 받으며, 동시에 전체 일수와 벌금의 합을 계산합니다.
3. 만약 전체 일수가 제출 기한과 같다면 모든 문제를 제출 기한 내에 풀 수 있으므로 벌금은 0원으로 출력합니다.
4. 그렇지 않은 경우, 다이나믹 프로그래밍(DP) 알고리즘을 사용하여 가능한 한 최소의 벌금을 계산합니다.
5. DP 테이블 dp[i][j]는 i번째 문제까지 고려하고, 제출 기한이 j인 경우의 최소 벌금을 나타냅니다.
6. DP 테이블을 채우며 최종적인 최소 벌금을 계산하고 출력합니다.