[백준][1062번][DPS] 가르침

스도쿠

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

<문제>

<코드>

#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <string.h>
 
using namespace std;
 
int n,k;
string word[50];
int know[26];
int ans = 0;
void dfs(int start, int cnt)
{
    // x는 배운 글자 갯수
    // k개의 글자를 다 배웠으면
    //cout << "x : " << x << endl;
    if(cnt==k)
    {
        int result = 0;
        for(int i=0;i<n;i++)
        {
            int flag = 1;
            // 한 줄 한 줄 체크
            for(int j=0;j<word[i].length();j++)
            {
                // 한 단어라도 모르면
                if(know[word[i][j]-'a'] == 0)
                {
                    flag = 0;
                    break;
                }
            }
            // 해당 문장 단어를 다 알면
            if(flag == 1)
                result++;
        }
        ans = max(ans, result);
    }
    for(int i=start;i<26;i++)
    {
        if(know[i] == 0)
        {
            know[i] = 1;
            dfs(i, cnt+1);
            know[i] = 0;
        }
    }
}
 
int main()
{
    cin >> n >> k;
    cin.ignore();
    
    // k가 5이하면 0이 정답
    if(k<5)
    {
        cout << 0;
        return 0;
    }
 
    for(int i=0;i<n;i++)
    {
        getline(cin,word[i]);
        word[i].erase(0,4);
        word[i].erase(word[i].length()-4,4);
    }
 
    know['a'-'a'] = 1;
    know['n'-'a'] = 1;
    know['t'-'a'] = 1;
    know['i'-'a'] = 1;
    know['c'-'a'] = 1;
    k-=5;
 
    dfs(0,0);
    cout << ans;
 
 
 
}
 

<문제 푼 요령>

1. 알파벳은 총 26개밖에 안되므로 학생들이 공부한 알파벳 배열 know[26]을 만들고 배운 알파벳 인덱스값을 1로 설정해준다. 

2. 학생들이 배운 단어 갯수가 k개를 만족한다면 배운 알파벳으로 단어를 몇개 읽을 수 있는지 계산해준다. (이에 따라서 미리 알고 있다고 설정한 5개의 단어를 제외해주기 위해서 k-=5를 해준다.)

3. k개를 다 배울 때 까지는 dfs로 골고루 배울 수 있도록 해준다. 이번에 string을 처음 다뤄봤는데 c에는 없던 자료형이 c++에는 있어서 좋은 것 같다. cin.ignore()와 getline()은 혹시 몰라서 쓴건데 저거는 string에서 공백까지 입력 가능하게끔 해주는 것이다.