[백준] 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - c++

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

문제

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

입력

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

출력

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

예제

문제 정의

처음엔 조합 재귀함수를 구현해서 3가지 경우의 수를 뽑을 때마다 안되는 조합인지 확인하는 로직으로 작성했었다.

하지만 이렇게 구현하니 조합을 구현할 때마다 반복문을 돌아야 했기에 시간초과가 났다.

<시간초과 난 코드>

#include<bits/stdc++.h>
using namespace std;
int n, m, a, b, cnt, total, res;
vector<int> v;
vector<pair<int, int>> no;

void print(vector<int> b) {
  for (int j = 0; j < no.size(); j++) {
    cnt = 0;
    for (int i: b){
      if (i == no[j].first || i==no[j].second)
        cnt++;
    }
    if (cnt >= 2) {
      res++;
      break;
    }
  }
  total += 1;
}

void combi(int start, vector<int> &b) {
  if (b.size() == 3) {
    print(b);
    return;
  }
  for (int i = start+1; i < n+1; i++) {
    b.push_back(i);
    combi(i, b);
    b.pop_back();
  }
  return;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    no.push_back({a, b});
  }

  combi(0, v);
  cout << total - res << "\n";
}

따라서 unordered_set을 이용하여 string 형식으로 안되는 조합을 저장했다.

그 후 모든 경우의 수를 반복문을 돌렸다.
n<=200 이므로 200x200x200 = 8000000 이므로 시간초과가 나지 않을 것 같았다.

모든 경우의 수 마다 안되는 조합이 있는지 확인하고 없을 경우 선택하는 경우의 수를 +1 했다.

#include<bits/stdc++.h>
using namespace std;
int n, m, a, b, cnt;
unordered_set<string> s;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    if (a > b)
      swap(a, b);
    s.insert(to_string(a) + "," + to_string(b));
  }

  for (int i = 1; i < n+1; i++) {
    for (int j = i+1; j < n+1; j++) {
      for (int k = j+1; k < n+1; k++) {
        if (s.count(to_string(i) + ","+ to_string(j)) ||
            s.count(to_string(i) + ","+ to_string(k)) ||
            s.count(to_string(j) + ","+ to_string(k)))
          continue;
        else
          cnt++;
      }
    }
  }
  cout << cnt << "\n";
}