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

N개의 아이스크림이 있고, 섞어 먹으면 안되는 M개의 아이스크림 조합의 개수가 주어질 때, 섞어 먹으면 안되는 조합을 피해 3개의 아이스크림을 고르는 경우의 수를 구하는 문제이다.

음...섞어 먹으면 안되는 아이스크림의 조합을 포함한 N-3개의 아이스크림을 고르는 경우의 수를 구하는 건 어떨까? 섞어 먹으면 안되는 아이스크림의 조합 하나당 아이스 크림이 2개 포함되어 있으므로 ( (N-2) C (N-3-2) ) * M 이 답이될 것이다.
이게 맞다면 입력으로 받는 N, M만 필요하고 섞어 먹는 아이스크림의 조합은 필요가 없다.
일단 구현해 봐야겠다.
음 틀렸다. 섞어 먹으면 안되는 아이스크림의 조합이 뭐냐가 중요하다.
위의 방법대로 할 경우 입력 예제로 예를 들면 (1, 2), (3, 4) (1, 3)이 섞어 먹으면 안되는 조합인데, (1, 2)를 포함한 N-3개 즉 2개의 아이스크림을 고르는 경우의 수는 (1, 2) 하나인데, 어떻게 이 예제에서는 답은 맞게 나오지만 사실 (1, 2)를 찾았으면 (3, 4, 5)가 답이 되어야하는데 그렇지 않다. (3, 4, 5)는 (3, 4)를 포함하고 있기 때문에 안된다.

다시 처음부터 생각해봐야 겠다.
결국 baactree님의 풀이를 봤다. 이게 N제한이 200이라 O(N세제곱)풀이를 이용하면 된다고 한다. 3중 for문으로 3개의 수를 뽑으면서 M개의 섞어 먹으면 안되는 조합이 포함되어있는 경우는 세지 않으면 된다고 한다. 여기서 M개의 섞어 먹으면 안되는 조합을 어떻게 체크할까 궁금했는데 arr[a][b], arr[b][a]에 기록해 놓으면 O(1)만에 체크할 수 있다... 쉬워 보이지만 난 전혀 생각하지 못했다.
그리고 3중 for문으로 할 경우 조합이 아닌 순열의 개수만큼 나온다. 하지만 중복된 것은 가능한 한 경우당 3*2*1 == 6가지로 같다. 그렇기 때문에 최종적으로 6으로 나누어 주면 된다.

아.. 아니구나 3중 for문으로 할 경우에도 조합을 구할 수 있구나... 처음 알았다.
i=1~n
 j=i+1~n
  k=j+1~n
이런 식으로 하면 될 것이다.... 헉.. 처음 알았다. 진짜...1을 포함한 조합을 다 구하고, 2를 포함한 조합을 다 구하고... 이렇게 2개짜리 조합(nC2)을 구할 때 처럼 nC3도 마찬가지구나..
good!

이 문제의 풀이를 보면서 느낀게... 내가 실력이 부족한데 그 것을 커버할 수 있는 방법 중 하나가 다양한 문제를 많이 풀어봐서 경험을 많이 쌓는 것인 것 같다.

일단 구현해 봐야겠다.
AC를 받았다. nC3를 , 조합을 for문으로 구현할 수 있다는 것을 알게된 좋은 문제였다.