[SWEA/D4] SWEA 3752 가능한 시험 점수(C++)

문제 출처

SW Expert Academy

 

알고리즘 분류

• 다이나믹 프로그래밍

풀이

점수의 개수가 총 100개이기 때문에, 경우의 수는 2^100가지이므로 백트래킹으로는 풀 수 없다.

따라서 DP로 해결해야 한다.

먼저 0점은 처음부터 가능하므로 DP[0] = true로 초기화한다.

그리고 다음 점수를 입력받으면 현재 점수의 Index * 100(== i)점부터 DP[i]가 true라면 DP[i + 점수] 역시 true가 된다.

첫 번째 테스트 케이스를 보자면, 처음에 2점을 입력받았으므로 DP[0 + 2]는 true가 된다.

그리고 다음 3점을 입력받았으므로 DP[2 + 3], DP[0 + 3]이 true가 된다.

여기서 0부터 따지게 될 경우 DP[0 + 3], 즉 DP[3]이 true로 미리 초기화가 되므로 3을 따질 때 DP[3]이 true라서 DP[3 + 3], 즉 DP[6]이 true가 되어버린다. 이것을 방지하기 위하여 현재 점수의 Index * 100부터 내림차순으로 따져야 한다.

이런 식으로 N개의 점수를 입력받으면서 0점부터 N * 100점까지 받을 수 있는 가능한 점수들을 모두 기록하고, 그 개수를 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int T, N;
int Case = 1;
int Number;
bool DP[MAX];
int Answer;

void init() {
    DP[0] = true;
    for (int i = 1; i < MAX; i++) {
        DP[i] = false;
    }
    Answer = 0;
}

void settings(int Index) {
    for (int i = (Index * 100); i >= 0; i--) {
        if (DP[i]) {
            DP[i + Number] = true;
        }
    }
}

void find_Answer() {
    for (int i = 0; i <= (N * 100); i++) {
        if (DP[i]) {
            Answer++;
        }
    }
    cout << "#" << Case++ << " " << Answer << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> Number;
            settings(i + 1);
        }
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}