[백준] 19949번 : 영재의 시험 (C++)

19949번 : 영재의 시험

---

문제)

컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다.

평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다.

당연하게도 문제를 하나도 풀지 못하였지만 다행히도 문제가 5지 선다의 객관식 10문제였다.

찍기에도 자신 있던 영재는 3개의 연속된 문제의 답은 같지 않게 한다는 자신의 비법을 이용하여 모든 문제를 찍었다.

이때 영재의 점수가 5점 이상일 경우의 수를 구하여라.

문제의 점수는 1문제당 1점씩이다.

 

 

 

입력 :

시험의 정답이 첫 줄에 주어진다.

 

 

 

 

출력 :

영재의 점수가 5점 이상일 경우의 수를 출력하여라.

 

 

 

 

 

풀이)

 

// 19949. 영재의 시험
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> vec;
 
int dp[10][6][6][10];
 
int recur(int cur, int pprev, int prev, int total)
{
    // 10번 문제까지 도달 했을 때
    if (cur == 10)
    {
        // 점수가 5점 이상이면 1 리턴
        if (total >= 5) return 1;
        // 5점 미만이면 0 리턴
        return 0;
    }
 
    // 이미 구한 값이라면, 값만 리턴해준다.
    if (dp[cur][pprev][prev][total] != -1)
    {
        return dp[cur][pprev][prev][total];
    }
 
    int ret = 0;
 
    for (int i = 1; i < 6; i++)
    {
        // 3개 연속 같은 숫자라면 continue
        if (pprev == prev && prev == i) continue;
        
        // 정답을 맞췄다면
        if (vec[cur] == i)
        {    // total에 +1을 해서 넘겨준다.
            ret += recur(cur + 1, prev, i, total + 1);
        }
        // 정답이 틀렸다면
        else
        {    
            ret += recur(cur + 1, prev, i, total);
        }
    }
 
    dp[cur][pprev][prev][total] = ret;
 
    return dp[cur][pprev][prev][total];
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    vec.resize(10, 0);
    for (auto& ele : vec) cin >> ele;
 
    fill(&dp[0][0][0][0], &dp[9][5][5][10], -1);
 
    cout << recur(0, 0, 0, 0);
    
    return 0;
}
 
 

---

출처 : https://www.acmicpc.net/problem/19949 

19949번: 영재의 시험