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

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

14728번: 벼락치기

Code:

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

문제 설명:

주어진 문제는 "ChAOS(Chung-ang Algorithm Organization and Study)" 회장이 되어 바빠진 준석이가 시험기간에도 일로 인해 공부를 제대로 하지 못하다가, 시험 전 날이 되어버린 상황에서, 교수님으로부터 받은 힌트를 활용하여 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하는 것입니다.

힌트 요약:

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에 한 문제를 출제하며, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.
3. 각 단원 별로 예상 공부 시간과 배점이 주어진다. 문제를 푸는데 필요한 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다.

코드 설명:

 

1. #define max(a, b) 매크로 함수를 정의하여 두 값 중에서 큰 값을 반환하도록 설정합니다.
2. 변수 n은 단원의 개수, 변수 t는 총 공부 시간을 나타냅니다.
3. dp 배열은 동적 계획법을 위한 메모이제이션을 위한 2차원 배열입니다. k 배열은 각 단원의 예상 공부 시간, s 배열은 배점을 저장합니다.
4. 이중 반복문을 사용하여 모든 가능한 경우를 탐색하며 최대 점수를 계산합니다.
5. dp[i][j]는 i번째 단원까지 고려하고, j 시간 동안 얻을 수 있는 최대 점수를 나타냅니다.
6. 점화식은 현재 시간 j에서 i번째 단원을 공부할 경우와 그렇지 않을 경우를 고려하여 최대값을 찾습니다.
7. 최종적으로 dp[n][t]에는 준석이가 얻을 수 있는 최대 점수가 저장되고, 이를 출력합니다.

이 코드는 동적 계획법을 활용하여 각 단원을 선택하거나 선택하지 않는 모든 경우를 고려하여 최대 점수를 계산하는 방법을 이용했습니다.