취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 19949번 문제인 영재의 시험이다.
문제는 아래 링크를 확인하자.

https://www.acmcipc.net/problem/19949 

10개의 오지선다 문제의 답을 아무렇게나 찍는 경우의 수는 $5^{10}$, 즉 9765625가지밖에 되지 않는다.

따라서 가능한 모든 오지선다 답안에 접근해 각각이 영재가 답할 수 있는 답안인지 및 점수가 5점 이상인지를 확인하는 완전탐색으로 이 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int A[10];
int pnt, cnt;
vector<int> vec;

void func(int idx) {
    if (vec.size() > 2 && vec[vec.size() - 3] == vec[vec.size() - 2] && vec[vec.size() - 2] == vec.back()) return;
    if (idx == 10) {
        if (pnt > 4) cnt++;
    }
    else {
        for (int i = 1; i < 6; i++) {
            vec.emplace_back(i);
            if (A[idx] == i) pnt++;
            func(idx + 1);
            vec.pop_back();
            if (A[idx] == i) pnt--;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 10; i++) cin >> A[i];
    func(0);
    cout << cnt;
}