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에서 최대한 가까운 값을 출력하였다.

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

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

#include 

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;
}