안녕하세요. 그리디로 문제를 해결했습니다. 근데 채점 사이트에서는 계속 sigsegv 에러가 떠서 질문올립니다. 제 알고리즘과 그 구현에 혹시 문제를 발견하신다면 고견 감사드립니다 ㅜㅜ

저는 ALLERGY 문제를 그리디 알고리즘으로 해결하려고 했어요.

먹을 수 있는 음식이 없는 학생들에 대해, 이 학생들을 최대로 먹이는 음식을 선택하면 최소 음식의 개수가 나온다고 생각했습니다.

그리디 속성 증명

1) 최소 음식 선택 골라 모든 학생 포함시키는 경우에서, 남아있는 사람에서 가장 많은 음식을 먹이는 경우가 포함 되지 않는 경우 모순 발생했습니다.
2) 특정 음식을 선택했을 때 남은 학생들과 음식의 수가 부분문제 구조를 만족 했습니다.

그래서 특정 음식을 선택하는 기준으로, 남은 학생들을 최대한 먹이는 방향으로 진행합니다. 그리고 모든 학생이 다 먹는 경우 선택한 음식 최소값을 리턴하는 걸로 구현했습니다.

제 컴퓨터에서 여러 예제 (10 ,15) (2,2) (1,1) 등에 대해서 다 맞는 결과가 나왔습니다. 근데 채점만 하면 계속 런타임 에러가 뜨더라구요.

초기 메모리 할당도 최대값에 맞추어 했고 test case 마다 필요 자료구조들 초기화도 다 했습니다. (M , N 이 최대 20)
제가 생각하는 빅오 노테이션은 메인 재귀 함수 O(N ) 재귀 당 루프 기준, O(M *N) 이어서 총 O(MN^2) 정도로 stack over flow가 날 규모는 아니라고 생각합니다.
또한 배열 인덱스 등 메모리 접근도 아무리 봐도 제대로 한 거 같습니다 ㅜㅜ

그리디 속성 증명에서 제가 잘 못 생각한 게 있을까요? 인풋 예시와 제가 만든 몇몇 예시는 다 정확한 결과가 나와서 질문드립니다.

구현 측면

/*** input ***/
M 이 음식 수, N이 학생 수일 때, 전체 3개의 table이 있습니다.

foodTable[음식][학생] : 음식들에 학생들이 먹을 수 있는거 표현
pickedFoodTable[음식]; 지금까지 고른 음식들
checkTable[학생]; 현재까지 고른 음식에 대해, 각자 먹는 음식이 있음을 표현
그리고 학생들은 map을 통해 저장했습니다. 문제에서는 string 이름을 idx로 다 변환해 사용합니다.
map friends;

알고리즘 구현
매 음식 마다, 현재 상황(음식먹인 학생 정보)에 대해 남은 음식들이 먹일 수 있는 학생 수를 갱신하는 과정이 들어갑니다. 코드 전문은 아래에 놔두겠습니다.

int solve(){
// 고른 음식들에 대해 모든 학생이 다 먹을 수 있으면 재귀를 그만합니다.
if(isAllTrueCheck()) return 0;

// key는 현재 checkTable에 대해 각 음식을 선택시 몇 명의 학생을 먹일 수 있는지 이고 value는 그 음식의 idx 입니다.  
vector< pair<int , int> > temp;
for(int i = 0; i < M; ++ i){
    if(not pickedFoodTable[i]){// 선택되지 않은 food 들에 대해,
        // 음식을 선택한다면, 몇 명의 학생을 추가적으로 먹일 수 있는지를 알아본다.
        int cnt = getIntersectNum(i); // 추가적으로 먹일 수 있는 학생의 수
        temp.emplace_back(make_pair(cnt, i));
    }
}
sort(temp.begin(), temp.end());

//가장 많이 먹일 수 있는 음식 번호
int pickedFoodIdx = temp.back().second;
// update
pickedFoodTable[pickedFoodIdx] = true;
updateCheckTable(pickedFoodIdx);

return 1+ solve();

}

##코드 전문##

/헤더들/

using namespace std;

int T;
int N;
const int MAX_N = 21;
int M;
const int MAX_M = 21;

map friends;
bool foodTable[MAX_M][MAX_N]; // 어떤 음식에 대해 (row) 특정학생(col)이 먹을 수 있으면 true, 아니면 false
bool checkTable[MAX_N]; // 학생들이 뭘 먹을 수 있고 먹을 수 없는지를 나타냄
bool pickedFoodTable[MAX_M]; // 처음엔 false, 음식을 추가할 때마다 true가 된다.

bool isAllTrueCheck(){
// chckTable이 모두 True인지 본다.
for(int i = 0; i < N; ++i)
if(not checkTable[i]) return false;

return true;

}

int getIntersectNum(int foodIdx){

int ret = 0;
for(int i = 0 ; i < N ; ++i)
    if(foodTable[foodIdx][i] and !checkTable[i] )++ret;

return ret;

}

void updateCheckTable(int pickedFoodIdx){
for(int i = 0 ; i < N ; ++i)
if(foodTable[pickedFoodIdx][i])
checkTable[i] = true;

}

int solve(){
if(isAllTrueCheck()) return 0;
vector< pair > temp;
for(int i = 0; i < M; ++ i){
if(not pickedFoodTable[i]){// 선택되지 않은 food 들에 대해,
// 이 음식 만든는 것을 선택한다면, 몇 명의 학생을 추가적으로 먹일 수 있는지를 알아본다.
int cnt = getIntersectNum(i); // 추가적으로 먹일 수 있는 학생의 수
temp.emplace_back(make_pair(cnt, i));

}
}
sort(temp.begin(), temp.end());

//가장 많이 먹일 수 있는 음식 번호
int pickedFoodIdx = temp.back().second;
pickedFoodTable[pickedFoodIdx] = true;
updateCheckTable(pickedFoodIdx);

return 1+ solve();

}

int main() {
ifstream inFile;
inFile.open("../input");
inFile >> T;

for(int test_case = 0; test_case < T; ++test_case){
    friends.clear();

// memset(foodTable, false, sizeof(bool) * MAX_M * MAX_N);
for(int i = 0; i < MAX_M; ++i){
for(int j = 0; j < MAX_N; ++j)
foodTable[i][j]= 0;
}

// memset(checkTable, false, sizeof(bool) * MAX_N);
for(int i = 0; i < MAX_N; ++i)checkTable[i]= 0;

// memset(pickedFoodTable, false, sizeof(bool) * MAX_M);
for(int i = 0; i < MAX_M; ++i)pickedFoodTable[i]= 0;

inFile >> N;inFile >> M;
    for(auto i = 0; i < N; ++i){
        string tmp; inFile>>tmp;
        friends.insert(make_pair(tmp, i));
    }

    for(auto i = 0; i < M; ++i){
        int t_num; inFile>> t_num;
        vector<string> tmp;
        for(auto j = 0; j < t_num; ++j){
            string t_tmp; inFile>>t_tmp;
            int friend_idx = friends[t_tmp];
            foodTable[i][friend_idx] = true;
        }
    }


    // ******************input 검증 완료

    int ans = solve();
    cout<<ans << endl;

}
return 0;

}

##인풋 파일 ##
4
4 3
a b c d
2 a d
1 a
3 a b c
10 15
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
2 a1 a4
1 a2
4 a3 a5 a8 a9
1 a10
2 a3 a4
5 a3 a4 a5 a6 a7
1 a2
1 a1
1 a6
1 a9
1 a10
1 a1
1 a1
1 a1
1 a1
4 6
cl bom dara minzy
2 dara minzy
2 cl minzy
2 cl dara
1 cl
2 bom dara
2 bom minzy
10 7
a b c d e f g h i j
6 a c d h i j
3 a d i
7 a c f g h i j
3 b d g
5 b c f h i
4 b e g j
5 b c g h i