SWEA 3752번: 가능한 시험 점수 (dp 이용)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

 

[문제]

영준이는 학생들의 시험을 위해 N개의 문제를 만들었다.
각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다.
학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까?
예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다
가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다.
두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 1점이다.
가능한 시험점수의 경우의 수를 살펴보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 모두 11가지이다.

 

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 자연수 N(1 ≤ N ≤ 100)이 주어진다.
두 번째 줄에는 각 문제의 배점을 의미하는 N개의 자연수가 공백으로 구분되어 주어진다. 배점은 1이상 100이하의 자연수이다.

[출력]
각 테스트 케이스마다 학생들이 받을 수 있는 점수의 경우의 수를 출력한다.

 

[입출력 예시]

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>


int main() {
	int tc;
	scanf("%d", &tc);

	for (int i = 1; i <= tc; i++) {
		//문제 수 입력 받기
		int prob_num;
		scanf("%d", &prob_num);
		
        //점수 입력 받기
		int prob[100];
		int max_score = 0;
		for (int j = 0; j < prob_num; j++) {
			scanf("%d", &prob[j]);
			max_score += prob[j];
		}
		
        //score[i]는 i점이 가능하면 1, 불가하면 0을 의미
		int score[10000] = { 0, };
		score[0] = 1;
		
        //dp로 해결하기
        // k-prob[j] 점이 가능하면 k점도 가능하고, 이미 k점이 가능하면 당연히 k점 가능함
		for (int j = 0; j < prob_num; j++) {
			for (int k = max_score; k >= prob[j]; k--) {
				score[k] = score[k] || score[k - prob[j]];
			}
		}
		
        //가능한 점수의 개수 세기
		int ans = 0;
		for (int j = 0; j <= max_score; j++) {
			if (score[j])
				ans++;
		}

		printf("#%d %d\n", i, ans);
	}
	return 0;
}