[SWEA] 3752 가능한 시험 점수

 

이 문제는 dp로 풀 수 있다

다 풀어놓고 혼자 문제에도 없는 조건을 한줄 추가해서 틀리고있었다..!

 

N이 100까지 들어오고 Ni는 1~100 사이 이므로 최대 10000점까지 받을 수 있다

그럼 dp를 이용해 d[100][10000] 테이블을 잡아서 i번째에 j점을 받을 수 있는지 살펴보자!

 

먼저 i-1번째에 받을 수 있는 점수 j 여야만 i번째에 확인해볼 수 있다!

예를들어 내가 N개의 수를 보고있을때 N-2에서 10점을 받았으면

N-1에서는 10점에 N-1번째 수를 더한 값도 받을 수있다..! 

이해가 갈지 모르겠으나 코드를 통해 보면 쉽게 확인 가능하다!

그렇게 N번째까지 받을 수 있는 점수를 dp로 찾아두고 

d[N][0~10000]을 볼 때 참인 값들은 우리가 받을 수 있는 점수이다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
bool d[110][10010];
int arr[111];
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        memset(d,0,sizeof(d));
        memset(arr,0,sizeof(arr));
        int n; scanf(" %d",&n);
        for(int i=1;i<=n;i++) scanf(" %d",&arr[i]);
        d[0][0]=1;
 
        for(int i=1;i<=n;i++){
            for(int j=0;j<=10000;j++){
                if(d[i-1][j]){
                    d[i][j]=1;
                    if(j+arr[i]<=10000) d[i][j+arr[i]]=1;
                }
            }
        }
 
        int ans=0;
        for(int i=0;i<=10000;i++) if(d[n][i]) ans++;
        printf("#%d %d\n",c++,ans);
    }
}

 

 

1차원 배열을 통해 풀 수도 있다!

숫자를 더하기만 하므로 가능한 점수는 커질 것이다

그러므로 10000 부터 0까지 거꾸로 가능한 점수를 보며 

가능한 점수에 현재문제를 맞은점수를 더해 새로운 점수를 추가해가면 된다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
bool d[10010];
int arr[111];
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        memset(d,0,sizeof(d));
        memset(arr,0,sizeof(arr));
        int n; scanf(" %d",&n);
        for(int i=1;i<=n;i++) scanf(" %d",&arr[i]);
        d[0]=1;
 
        for(int i=1;i<=n;i++){
            for(int j=10000;j>=0;j--){
                if(d[j]) d[j+arr[i]]=1;
            }
        }
 
        int ans=0;
        for(int i=0;i<=10000;i++) if(d[i]) ans++;
        printf("#%d %d\n",c++,ans);
    }
}