[C++] SWEA 3752 - 가능한 시험 점수

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

SW Expert Academy

<풀이>

1. 문제의 배점들을 입력받는다.

2. 배점들로 만들 수 있는 점수의 가짓수를 출력한다.

 

<해법>

1. 점수의 가짓수를 계산하는 방법

=> 예를 들어서 설명해보겠습니다. 만약, 주어진 배점들로 만들 수 있는 점수가 0, 3, 5, 8, 10이고, 새로운 문제의 배점은 5점이라고 가정하겠습니다. 이 때, 만들 수 있는 새로운 점수는 기존에 가지고 있던 점수에 새로운 문제 배점을 더한 값들일 것입니다. 0+5, 3+5, 5+5, 8+5, 10+5 -> 5, 8, 10, 13, 15 입니다. 여기서 5, 8, 10은 중복된 값이므로 제외하면, 만들 수 있는 점수들은 0, 3, 5, 8, 10, 13, 15 입니다. 따라서, 기존에 만들 수 있는 점수들에 새로운 문제 배점들을 더해가면서 만들 수 있는 점수를 늘려갑니다.

 

#include <iostream>
#include <string.h>
#include <vector>
 
using namespace std;
 
int N;
int score[100];
bool visited[10001];
vector<int> canScore;
int answer;
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        memset(score, 0, sizeof(score));
        memset(visited, false , sizeof(visited));
        canScore.clear();
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> score[i];
        }
 
        //해법
        //0점부터 시작
        canScore.push_back(0);
        visited[0] = true;
 
        for (int i = 0; i < N; i++) {
            
            //현재 만들 수 있는 점수의 개수(벡터 사이즈) 저장
            int v_size = canScore.size();
 
            for (int j = 0; j < v_size; j++) {
 
                //새로운 점수 = 현재 만들 수 있는 점수 + 새로운 배점
                int newScore = canScore[j] + score[i];
 
                //이전에 만들 수 있는 점수가 아닌 경우 -> 벡터에 저장
                if (!visited[newScore]) {
                    canScore.push_back(newScore);
                    visited[newScore] = true;
                }
            }
        }
 
        //결과 갱신
        answer = canScore.size();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

수학적인 사고에 대해 알아볼 수 있는 문제였습니다.

---

위 문제보다 조금 더 어렵지만, 같은 사고를 이용하여 푸는 문제입니다. 아래 문제도 풀어보시면 도움이 될 것 같습니다!

www.acmicpc.net/problem/2437

2437번: 저울