[Algorithm]Boj 2422 cpp

2422

• 아이스크림 종류 N, 피해야 할 조합 수 M개가 주어진다.

• 그 다음 M 줄로 피해야할 두 아이스크림의 조합이 주어진다.

  풀이

• 가능한 모든 아이스크림의 조합을 모두 돌리면서 (완전탐색)

• 피해야 할 조합을 모두 돌려보면서, 돌리고 있는 아이스크림의 조합이 피해야할 조합을 가지고있다면 그냥 끝낸다.

• 만약 피해야 할 조합을 모두 통과했다면 count를 증가시켜준다.

• 위 방법대로 하면 시간초과가 뜬다.

• 200 199 198 * 10000 = 788억이기 때문..

• 그럼 줄일 수 있는게 어떤게 있을까?

• 아이스크림은 모두 확인을 해봐야 하긴 한다. 왜냐면 가능한 가짓수를 세야하니까..

• 그러면 check하는 저 연산을 줄여야 하는데, 어떻게 하면 두 조합을 묶어서 의미있게 저장할 수 있으며 동시에 신속하게 할 수 있을까?

• 나 같은 경우 처음엔 pair를 사용해서 구현하였다.

• 배열을 생각하지 않았던게, 1차원 배열에 구현한다면 피하지 않아도 될 조합도 check에서 통과되지 않을 수 있기 때문이다.

• 하지만 2차원배열을 생각을 못했다.. 2차원 배열을 이용한다면 속도가 빠르게 구현이 가능하다.

• 주의해야 할 점은, 피해야 할 조합은 오름차순으로 들어오지 않을 수 있다.

• 따라서 2차원 배열의 행(왼쪽거) 보다 열(오른쪽거) 이 더 크도록 넣어주면 오름차순으로 넣어줄 수 있고, 가능한 아이스크림의 조합을 돌릴때 오름차순으로 넣어주면 정확하게 비교할 수 있다.

  코드

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  int check_list[200][200];
  
  int check(int i, int j, int k)
  {
  	if (check_list[i][j] != 1 && check_list[j][k] != 1
  			&& check_list[i][k] != 1)
  		return (1);
  	return (0);
  }
  
  int run(int N)
  {
  	int count = 0;
  	for (int i = 0; i < N - 2; i++)
  		for (int j = i + 1; j < N - 1; j++)
  			for (int k = j + 1; k < N; k++)
  				if (check(i, j, k))
  					count++;
  	return (count);
  }
  
  int main(void)
  {
  	ios_base::sync_with_stdio(0); cin.tie(0);
  	int N, M;
  	vector<pair<int, int> > sep;
  
  	cin >> N >> M;
  	for (int i = 0; i < M; i++)
  	{
  		int a, b;
  		cin >> a >> b;
  		a--;
  		b--;
  		if (a < b)
  			check_list[a][b] = 1;
  		else
  			check_list[b][a] = 1;
  	}
  	cout << run(N) << endl;
  }