(C++) - 백준(BOJ) 2422 : 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

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

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

모든 경우의 수를 구하는 brute force문제였습니다.

📕 풀이방법

📔 입력 및 초기화

 1. n, m, cnt, 불가한 아이스크림 조합을 그래프 형태로 저장할 vector graph, 뽑은 아이스크림 조합을 저장할 combCk를 선언 후 n, m에 입력받습니다. 2. m만큼 불가한 조합을 a, b를 입력받았을 때 인접리스트 형태로 그래프를 graph에 저장해줍니다.

📔 풀이과정

next_permutation을 이용해 nC3의 모든 조합을 뽑아냅니다. n이 최대 200, 최악은 200C3 = 1313400이므로 시간초과가 나지 않습니다. 뽑아낸 3개의 아이스크림 조합에서 또 2개를 골라 인접리스트 graph에 간선으로 존재하는지 확인해줍니다. 간선으로 존재한다면 해당 아이스크림 조합은 유효하지 않습니다. 2개를 고르는 모든 조합을 확인해 유효한 조합이라면 cnt++해줍니다.

📔 정답출력

cnt를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
vector <int> graph[201], combCk;

bool isValid(int s, int e){
    for(auto next : graph[s]) {
        if(next == e) return false;
    }
    return true;
}

int main(){
    cin >> n >> m;
    for(int i = 0,a,b; i < m; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    combCk.resize(n, 1);
    for(int i = 0; i < 3; i++) combCk[i] = 0;
    do{
        int can = 1;
        vector<int> tmp;
        for(int i = 0; i < n; i++) {
            if(!combCk[i]) tmp.push_back(i+1);
        }

        for(int i = 0; i < 3; i++){
            for(int j = i + 1; j < 3; j++){
                if(!isValid(tmp[i], tmp[j])) { can = 0; break; }
            }
        }
        if(can) cnt++;
    }while(next_permutation(combCk.begin(), combCk.end()));
    cout << cnt;
}