NORMAL2 수강신청

입력조건

출력조건

입력	출력
1 4 13 2 4 6 8	Case #1 12

dp를 이용해 해당 이수 학점을 들을 수 있을 때는 1, 없을 때는 0으로 저장하였다.

해당 학점(temp)에서 각 학점(sub[i])을 뺐을 때 나오는 학점을 들을 수 있다면,(dp[temp-sub[i]]==1) 해당 학점도 들을 수 있게 된다.

1학점부터 M학점까지 계산하였고, M에서 최대한 가까운 값을 출력하였다.

최적화로 생각해 볼 것은 각 케이스마다 배열을 동적 할당하여 메모리를 줄이는 방법과, 문제에 설명이 안되있지만 과목이 크기순으로 정렬을 확인하는 점이다.

문제에 제대로 설명이 안되어 있는데, 과목을 중복으로 들어도 되게 코딩을 했는데 통과한 걸 보면 중복으로 들어도 되나보다(대학 강의를 어떻게 중복으로 듣나..)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

#include <stdio.h>   int main(void) {     setbuf(stdout, NULL);       int dp[10001] = { 0 }; //해당 학점을 들을 수 있는가?     int sub[5000] = { 0 };     int i, j;     int T;     int test_case;     int N, M;     int temp;     int ans;     scanf("%d", &T);     for (test_case = 1; test_case <= T; test_case++) {           scanf("%d %d", &N, &M);         for (i = 0; i < N; i++) {             scanf("%d", &sub[i]);             dp[sub[i]] = 1; //각 과목에 해당하는 학점은 들을 수 있으므로 1로 저장         }         temp = 1;         while (temp <= M) {             if (dp[temp]) { //이미 해당 학점을 들을 수 있으면 스킵                 temp++;             }             else {                 for (i = 0; i < N; i++) { //해당 학점에서 각 과목 학점을 뺀 학점을 들을 수 있고, 각 과목 학점이 해당학점 보다 작은 경우 해당 학점도 들을 수 있다.                     if (dp[temp - sub[i]] && sub[i] <= temp) {                         dp[temp] = 1;                         break;                     }                 }                 temp++;             }         }         ans = M;         while (!dp[ans]) {             ans--;         }           printf("Case #%d\n", test_case);         printf("%d", ans);           for (i = 1; i <= M; i++) {             dp[i] = 0;         }                   for (i = 0; i < N; i++) {             sub[i] = 0;         }     }       return 0; } </stdio.h>