[BOJ] 출근 기록 - Compy's Blog

출근 기록

TimeLimit	MemoryLimit	Condition	TAG
2s	512MB	(1 ≤ S ≤ 50)	Dynamic Programming

일단 골드 2에서 그냥 그리디로 접근하다가 머리 깡 당하고 다시 생각하다보니 dp인 것 같아서 풀긴 했는데요

아직도 이해가 안되는건 골2가 왜 5차원 dp를 사용하는거죠? 뭐 더 간결하게 풀 수 있을지는 잘 모르겠지만 어허허허허허허허헣.. 쉽지 않네요…

무슨 문제만 보면 솔루션이 바로 안 떠오르면 자연스럽게 dp로만 생각하게 되는데 이런 버릇도 좀 고치고 싶네요

정답 코드

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>

#define mod 1000000LL

using namespace std;
using ll = long long;
string n;

int counts[3];

bool dp[51][51][51][4][4]; // a, b, c, 전 번호, 전전 번호
char result[51];

bool solution(int a, int b, int c, int past, int pastpast){
    
    if(a < 1 && b < 1 && c < 1) return true;
    
    if(dp[a][b][c][past][pastpast]) return false;
    
    dp[a][b][c][past][pastpast] = true;
    
    
    result[a+b+c] = 'C';
    if(c > 0 && !(pastpast == 3 || past == 3)){ // C가 없는 경우
        if(solution(a,b, c-1, 3, past)) return true;
    }
    
    result[a+b+c] = 'B';
    if(b > 0 && past != 2){

        if(solution(a,b-1, c, 2, past)) return true;
    }
    
    
    result[a+b+c] = 'A';
    if(a > 0){
        if(solution(a-1, b, c, 1, past)) return true;
    }
 
    
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(char i : n) counts[i-'A']++;
    
    int a = counts[0], b = counts[1], c = counts[2];
    
    
    if(!solution(a, b, c, 0, 0)) cout << -1;
    else{
        for(int i = 1; i <= n.size(); i++) cout << result[i];
    }
    return 0;
}