[C++] 백준 2422번:한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (브루트포스 알고리즘)

문제링크

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

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

문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

 

풀이

1. 조합이 불가능한 경우를 2차원 벡터에 담는다. (2차원 배열도 상관없음)

ex)

v[3][0] = 6일 경우 3과 6이 조합이 될 수 없는 경우다.

v[1][0] = 2일 경우 1과 2가 조합이 될 수 없는 경우다.

 

2. 전체 맛의 조합이 가능한 경우를 돌면서 3,4번을 반복한다.

3. 1번, 2번 맛이 조합이 가능한 경우를 찾고

4. 1번, 2번, 3번 맛이 조합이 가능한 경우를 찾아 개수를 세어준다.

 

글로 보면 간단하지만 flag와 index를 많이 사용하기 때문에 코드가 조금 복잡해 보일 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int n, m, a, b, cnt;
vector<int> v[201];    // 조합이 안되는 아이스크림을 담아둘 벡터
 
int main() {
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    // 조합
    for (int a = 1; a <= n - 2; a++) {
        for (int b = a + 1; b <= n - 1; b++) {
            bool possible = true;    // 1,2 맛이 섞이면 안되는 경우를 위한 flag
            for (int i = 0; i < v[a].size(); i++) {
                // 1,2 조합 확인
                if (b == v[a][i]) {
                    possible = false;
                    break;
                }
            }
            // 1,2가 조합이 가능한 경우라면 3을 찾으러 이동
            if (possible == true) {
                for (int c = b + 1; c <= n; c++) {
                    bool pos = true;    // 1,3/2,3 맛이 섞이면 안되는 경우를 위한 flag
                    // 1,3 조합 확인
                    for (int j = 0; j < v[a].size(); j++) {
                        if (c == v[a][j]) {
                            pos = false;
                            break;
                        }
                    }
                    // 2,3 조합 확인
                    for (int j = 0; j < v[b].size(); j++) {
                        if (c == v[b][j]) {
                            pos = false;
                            break;
                        }
                    }
                    // 1,2,3 조합이 가능할 경우 count
                    if (pos == true) {
                        cnt++;
                    }
                }
            }
        }
    }
 
    cout << cnt;
    
}

 

메모

같은 알고리즘을 사용하는 다른 문제이다.

[C++] 백준 2503번:숫자 야구 (브루트포스 알고리즘)