boj 14238 출근 기록

https://www.acmicpc.net/problem/14238

14238번: 출근 기록

 

dp[a][b][c][pre1][pre2]: 현재까지 A, B, C가 각각 a, b, c번 출근하였고, 전날 출근을 pre1, 전전날 출근을 pre2가 했을 때 올바른 출근 기록인지 여부

 

1일마다 A, B, C 중 한 명이 무조건 출근하며

A: 매일 출근할 수 있다.

B: 출근한 다음날은 반드시 쉬어야 한다.

C: 출근한 다음날과 다다음날은 반드시 쉬어야 한다.

위 조건들을 이용해서 구현 해야 합니다.

 

리턴 받은 값이 1이면 올바른 출근기록이므로 순서대로 출력해주시면 됩니다.

0을 리턴받았으면 올바른 출근기록이 없으니 -1을 출력합니다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#define MAX 51
using namespace std;
 
string str;
int dp[MAX][MAX][MAX][3][3];
int cnt[3];
int N;
 
int dfs(int a, int b, int c, int pre1, int pre2) {
    if (a + b + c == N) return 1;
    int &ret = dp[a][b][c][pre1][pre2];
    if (ret != -1) return ret;
    ret = 0;
 
    if (a < cnt[0]) {
        ret = dfs(a + 1, b, c, 0, pre1);
        if (ret == 1) {
            cout << 'A';
            return ret;
        }
    }
 
    if (b < cnt[1]) {
        if (pre1 != 1) {
            ret = dfs(a, b + 1, c, 1, pre1);
            if (ret == 1) {
                cout << 'B';
                return ret;
            }
        }
    }
 
    if (c < cnt[2]) {
        if (pre1 != 2 && pre2 != 2) {
            ret = dfs(a, b, c + 1, 2, pre1);
            if (ret == 1) {
                cout << 'C';
                return ret;
            }
        }
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    if (!dfs(0, 0, 0, 0, 0)) cout << "-1\n";
}
 
void init() {
    N = str.size();
    for (int i = 0; i < N; i++) {
        cnt[str[i] - 'A']++;
    }
}
 
void input() {
    cin >> str;
    init();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}