[cpp 알고리즘] 백준 2422 한윤정이 이탈리에아 가서 아이스크림을 사먹는데

[백준] 2422 한윤정이 이탈리에아 가서 아이스크림을 사먹는데 cpp 풀이

알고리즘: 브루트포스 알고리즘

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

문제 요약

- 아이스크림은 1부터 N까지 N종류의 아이스크림이 있다.

- M은 섞어 먹으면 안 되는 조합의 개수이다.

- 아이스크림 맛을 3가지 선택할 때, 섞어 먹어도 되는 조합은 몇 가지인지 구하면 된다.

풀이 정리

1. 조합(nC3)을 이용하여 가능한 모든 경우를 구하고, 섞어 먹어도 되는 조합인지 확인하는 방법을 생각했다.

2. 하지만 N의 최대 개수가 200 이었기 때문에, 더 단순하게 삼중 for문으로 구해보았다.

3. 3가지 아이스크림이 서로 같이 먹어도 되는 조합인지 확인하기 위해서 vector 안에 배열을 넣어 두어, 두 숫자가 같은 조합인지 확인했다. 

백준 2422 풀이

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> v[201];

bool canmix(int a, int b){
    for(int i=0; i<v[a].size(); i++){
        int temp = v[a][i];
        if(temp==b) return false;
    }
    return true;
}

int main(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int ans=0;
    
    for(int i=1; i<=N-2; i++){
        for(int j=i+1; j<=N-1; j++){
            for(int k=j+1; k<=N; k++){
                if(canmix(i,j) && canmix(i,k) && canmix(j,k)) ans++;
            }
        }
    }
    
   cout << ans << "\n";
    
    return 0;
}