[SW Expert] #2817 부분수열의 합

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

SW expert 해결했던 문제 중 가능한 시험 점수라는 포스팅에서 해결했던 방법을 사용하면 해결할 수 있을 거라 생각했다. 이는 정확한 해결방법이었다

---

2. 코드

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int total = 0;
int N = 0;
int K = 0;
int ary[20];
int temp[100000];
int sum = 0;

void check(){
    temp[0] = 1;
    sum = 0;
    
    for(int i = 0; i < N; i++){
     sum += ary[i];
        for(int j = sum; j>=0; j--){
            if(temp[j]){
                temp[j + ary[i]] += temp[j];
            }
        }
    }

}
int main()
{
    cin >> total;
    for(int i = 0; i < total; i++){
        memset(temp, 0, sizeof(temp));
        memset(ary, 0, sizeof(ary));      
        scanf("%d", &N);
        scanf("%d", &K);
        for(int j = 0; j < N; j++){
            scanf("%d", &ary[j]);
        }
        check();
        cout << "#" << i+1 << " " << temp[K] << endl;
    }
}

---

3. 주의사항

문제처럼 K의 범위를 1000으로 하면 런타임 에러가 발생하여 temp배열의 크기를 더 크게 설정해주었다