16508번 전공책

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

백트래킹 문제라고 생각하였으나, 잘 접근하지 못 하였다.

그래서 그냥 단순 구현으로 작성해보았으나, 반례가 있어서 잘 안 풀렸다.

맨 아래가 코드가 내가 작성한 코드이다.(틀린 코드임.)

그래서 다른 분의 코드를 보았더니, 역시 백트래킹으로도 풀 수 있는 문제였다.

백트래킹에 대해 더 열심히 해야겠다.

참고로, 해당 문자의 '개수'가 중요한 것이었다.

순서는 아래처럼 작성하여도 된다.

    used[pos] = true;
    sum += cost[pos];
    BackTracking(pos + 1);
    
    used[pos] = false;
    sum -= cost[pos];
    BackTracking(pos + 1);

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int INF, result;
 
int N = 0, sum = 0;
int letter[26] = { 0, }; // 원하는 단어에 대한 해당 문자 개수
int cost[16] = { 0, }; // 전공책 가격
int book[16][26] = { 0, }; // [a][b] : a 번째 책에 해당하는 책 이름에 대한 해당 문자 개수
int cnt[26] = { 0, };
 
bool used[16] = { false, }; // 책 사용 여부
 
void BackTracking(int pos)
{
    if (pos == N)
    {
        memset(cnt, 0, sizeof(cnt));
 
        for (int i = 0; i < N; i++)
        {
            if (!used[i]) continue;
 
            for (int j = 0; j < 26; j++)
            {
                cnt[j] += book[i][j];
            }
        }
 
        for (int i = 0; i < 26; i++)
        {
            if (cnt[i] < letter[i]) return;
            // 내가 원하는 어떤 단어의 해당하는 문자의 개수가 더 많다면,
            // 이 원하는 단어를 만들 수 없는 경우이므로, return
        }
 
        result = min(result, sum);
 
        return;
    }
 
    BackTracking(pos + 1);
    used[pos] = true;
    sum += cost[pos];
 
    BackTracking(pos + 1);
    used[pos] = false;
    sum -= cost[pos];
}
 
int main(void)
{
    INF = INT32_MAX;
    result = INF;
 
    string T;
 
    cin >> T;
 
    for (int i = 0; i < T.length(); i++)
    {
        ++letter[T[i] - 'A'];
    }
 
    scanf("%d", &N);
 
    int C = 0;
    string W;
 
    for (int i = 0; i < N; i++)
    {
        cin >> C >> W;
 
        cost[i] = C;
 
        for (int j = 0; j < W.length(); j++)
        {
            ++book[i][W[j] - 'A'];
        }
    }
    
    BackTracking(0);
 
    if (result == INF) printf("-1\n");
    else printf("%d\n", result);
 
    return 0;
}

<내가 작성한 코드. 틀린 코드이다.>

반례

AB

3

10 A

15 B

10 B

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef struct Book
{
    int money;
    string name;
}Book;
 
string Word;
 
int N = 0;
 
vector<Book> v;
 
bool isUsedBook[20] = { false, };
bool isUsedChar[20] = { false, };
 
int main(void)
{
    int bookMoney = 0, result = 987654321;
 
    bool isCalc = false;
 
    string bookTitle;
 
    cin >> Word;
 
    int wordSize = Word.size();
 
    cin >> N;
 
    Book book;
 
    for (int i = 0; i < N; i++)
    {
        cin >> bookMoney >> bookTitle;
 
        book.money = bookMoney;
        book.name = bookTitle;
 
        v.push_back(book);
    }
 
    int index = 0;
 
    int Count = N;
 
    bool isCheck[20][55] = { false, };
    memset(isCheck, false, sizeof(isCheck));
 
    while (Count--)
    {
        for (int i = index; i < N; i++)
        {
            string s = v.at(i).name;
 
            int sSize = s.size();
 
            for (int j = 0; j < wordSize; j++)
            {
                for (int k = 0; k < sSize; k++)
                {
                    if (Word[j] == s[k])
                    {
                        if (isUsedChar[j] || isCheck[i][k]) continue;
                        // 이미 원하는 단어 안의 '문자'를 검사했거나 입력한 책의 제목 안의 '문자'가 검사를 당했다면, 무시한다.
 
                        // 인덱스로 검사, 사용 여부를 판별한다. 0 ~ 
 
                        isCheck[i][k] = true; // i번 째 책의 k번 째 '문자' 사용 여부
                        isUsedBook[i] = true; // i번 째 책의 사용 여부
                        isUsedChar[j] = true; // 입력한 원하는 단어의 j번 째 '문자' 사용 여부
 
                        break;
                    }
                }
            }
 
            int Length = 0;
 
            for (int j = 0; j < wordSize; j++)
            {
                if (isUsedChar[j])
                {
                    // 원하는 단어에서 사용된 문자라면, Length 증가
                    ++Length;
                }
            }
 
            // 그 Length가 원하는 단어의 길이와 같다면
            if (Length == wordSize)
            {
                int caseSumMoney = 0;
 
                isCalc = true; // 계산 여부 표시
 
                for (int j = 0; j < N; j++)
                {
                    if (isUsedBook[j])
                    {
                        // j번 째 책이 사용되었다면
 
                        caseSumMoney += v.at(j).money;
                        // 돈 적립
                    }
                }
 
                result = min(result, caseSumMoney);
                // 최솟값을 구한다.
 
                memset(isUsedBook, false, sizeof(isUsedBook));
                memset(isUsedChar, false, sizeof(isUsedChar));
                memset(isCheck, false, sizeof(isCheck));
                // 한 번 계산 완료하였으니, 다음 번 계산을 위해 모두 초기화 한다.
                
                break; 
                // 한 번의 계산이 완료된다면, 다음 순서에 있는 책에 대한 기준으로 넘어간다.
            }
        }
 
        ++index; // 따라서, index가 1 증가한다. 동시에, Count는 1 감소한다.(while문 조건)
    }
    
    if(isCalc) cout << result << '\n';
    else cout << "-1\n"; // 계산을 한 적이 없다면, -1 출력
    
    return 0;
}