[SWEA] 3752번 가능한 시험 점수

3752번 가능한 시험 점수

문제 링크

 

해결방법

반복문을 통해 가능한 경우의 수를 구하는 문제이다

N ≤ 100 이기 때문에, 완전탐색을 수행한다면, O(2^100) 의 시간이 걸리므로 불가능하다

조건을 분석한 뒤, 2중 반복문을 통해 해결할 수 있는 솔루션을 발견했다

 

 

⭐️ 솔루션 ⭐️

최대 배점은 100점 이고 최대 문제 수는 100개 이기 때문에 최고 점수는 10,000점 이다

0점의 경우부터 탐색을 시작한다

• 초기에, 0점의 플래그를 true 로 설정한 뒤, 벡터에 넣는다

• 각 배점을 반복문으로 돌며 아래와 같은 탐색을 수행한다

  • 벡터의 값을 꺼내, 현재 배점을 더한다
  • 만약 더한 값이 플래그 처리가 되지 않았다면, 플래그 처리 후 벡터에 넣는다

• 반복문을 모두 돌았다면, 벡터의 크기를 반환한다

 

 

소스코드

문제 해결 시간 : 1h 30m

메모리 : 12784 KB

시간 : 69 ms

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int testcase;
int n;
int score[101];
bool chk[10001];

vector<int> v;

int solve(){
    chk[0] = true;
    v.push_back(0);
    
    for(int i=1; i<=n; i++){
        int len = (int) v.size() - 1;
        
        for(int j=len; j>=0; j--){
            int now = v[j];
            int nxt = now + score[i];
            
            if(!chk[nxt]){
                v.push_back(nxt);
                chk[nxt] = true;
            }
        }
    }
    
    return (int)v.size();
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        cin >> n;
        
        for(int i=1; i<=n; i++){
            cin >> score[i];
        }
        
        memset(chk, false, sizeof(chk));
        cout << "#" << tc << " " << solve() << "\n";
        
        v.clear();
    }
    
    return 0;
}