[SWEA] 4223 - 삼성이의 트라우마

https://www.swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKpmwua-VoDFAUV

(이 글이 문제가 될 시 삭제하도록 하겠습니다.)

과거 삼성전자 SW Test A형을 딸 때 1시간 만에 풀었는데 복원문제라는 소문 듣고 풀어봤다

아주 살짝 더 쉬운 문제인데... 더 오래걸린... 이제 코딩아이디어가 빠르게 안되나보다...

1. SAMSUNG 문자열을 target배열에 각 문자의 갯수를 저장한다.

2. 그리고 나서 L, 면접관 이름, 점수 P를 입력받는다.

3. 조합으로 dfs탐색

   이때 중요한 것은 check배열에 면접관의 이름에 있는 문자의 갯수를 더하고 빼주며 검사한다

4. 매번 검사하며, target에 있는 문자의 갯수보다 작으면 그냥 넘어가고, 갯수가 충분하다면 최소값 찾고 리턴

5. 만들 수 없는 조건은 모두 더했을 때, 즉 깊이가 N과 같고, 갯수가 불충분한 경우 뿐!

   여기서 flag를 달아서 바로 리턴시켜도 되지만 귀찮아서 그냥 답이 초기값과 같으면 -1을 출력했다.

   이거 조절하면 시간을 더 줄일 수 있을 듯

#include <iostream>
#include <cstring>
#include <memory.h>
#define MX 12
#define INF 987654321
using namespace std;
 
int check[30], target[30], LP[MX][2];
char str[MX][MX];
int T, N, P, L, dab;
 
bool make()
{
    for (int i = 0; i < 26; i++)
        if (target[i] > check[i]) return false;
    return true;
}
 
void dfs(int d, int pos, int sum)
{
    if (d == N && !make()) return;
    if (make())
    {
        if (dab > sum) dab = sum;
        return;
    }
 
    for (int i = pos; i < N; i++)
    {
        for (int j = 0; j < LP[i][0]; j++)
            check[str[i][j] - 'A']++;
        dfs(d + 1, i + 1, sum + LP[i][1]);
        for (int j = 0; j < LP[i][0]; j++)
            check[str[i][j] - 'A']--;
    }
}
 
int main(void)
{
    char tmp[10] = { "SAMSUNG" };
    for (int i = 0; i < strlen(tmp); i++)
        target[tmp[i] - 'A'] ++;
 
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        memset(str, 0, sizeof(str));
        memset(LP, 0, sizeof(LP));
        dab = INF;
        cin >> N;
 
        for (int i = 0; i < N; i++)
        {
            cin >> LP[i][0];
            for (int j = 0; j < LP[i][0]; j++)
                cin >> str[i][j];
            cin >> LP[i][1];
        }
        dfs(0, 0, 0);
        cout << "#" << tc << " ";
        if (dab == INF) cout << -1 << endl;
        else cout << dab << endl;
    }
    return 0;
}