코드업 3510:예산 관리

문제 설명

정보 선생님은 예산이 많은 부서에서 일하고 있다.

학기말이 가까워지면서 부서의 예산을 가급적 모두 집행해야 될 상황이 되었다.

정보 선생님은 예산 범위를 넘지 않는 범위 내에서 다양한 활동을 하고 싶어한다.

지금 남은 예산(B)이 40이고(단위:만원), 예산을 사용할 수 있는 활동(N)이 6개가 있다.

6개의 활동에 각각 드는 비용은 7, 13, 17, 19, 29, 31이다.

여기서 40을 채울 수 있는 활동의 개수는 상관이 없다.

40을 넘지 않는 범위에서 활동 비용을 조합해보면,

7 + 13 + 17 = 37

7 + 31 = 38

7 + 13 + 19 = 39

...

따라서 40을 초과하지 않으면서 예산을 최대로 사용할 수 있는 비용은 39이다.

정보 선생님을 도와 줄 수 있는 프로그램을 작성하시오.

 

입력

첫째 줄에 남은 예산(B)가 입력된다. ( 10 <= B <= 35,000 )

둘째 줄에 예산을 사용할 수 있는 활동의 수(N)이 입력된다. (1 <= N <= 21 )

셋째 줄에 공백을 기준으로 N개의 활동비가 양의 정수로 입력된다.

 

출력

남은 예산을 초과하지 않으면서 최대로 사용할 수 있는 비용액을 출력하시오.

 

입력 예시

40

6

7 13 17 19 29 31

 

출력 예시

39

 

나의 코드

 

#include <stdio.h>

int main() {
    int b, n, num[21]; // 변수선언
    int dp[35001] = {0};	// 배열 생성
    scanf("%d", &b);	// 입력
    scanf("%d", &n);

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

    for (int i = 0; i < n; i++) {
        for (int j = b; j >= num[i]; j--) {
        	// 비교하면서 최댓값 비교
            dp[j] = (dp[j] > dp[j - num[i]] + num[i]) ? dp[j] : dp[j - num[i]] + num[i];
        }
    }

    printf("%d\n", dp[b]);	// 출력
    return 0;
}

 

문제 바로가기:https://codeup.kr/problem.php?id=3510&rid=0