풀이 아이디어

완전 탐색, 브루트포스

아이스크림을 n가지 중에서 3가지를 고르는데 (1<=N<=200)
섞어 먹으면 안 되는 조합을 boolean[][] isNotMix에 저장한다.
3중 for문으로 되는 조합을 완전탐색해 섞어먹어도 되는 경우만 카운트한다.
N이 최대 200이므로 $O(N^3)= 8,000,000$이므로 메모리나 시간 초과가 발생하지 않는다.

// 섞으면 안되는 경우 제외
if(isNotMix[i][j] | isNotMix[i][k] | isNotMix[j][k]){
	continue;
}

풀이 코드

import java.util.*;
import java.io.*;
public class _2422 {
    public static void main(String[] args) throws IOException{
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 아이스크림 종류의 수
        int m = Integer.parseInt(st.nextToken()); // 섞어먹으면 안되는 조합의 수
        boolean[][] isNotMix = new boolean[n+1][n+1]; // 섞어먹으면 안되는 조합 저장
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            isNotMix[x][y] = true;
            isNotMix[y][x] = true;
        }
        // 아이스크림 조합 계산
        int answer = 0;
        for(int i=1;i<=n-2;i++){
            for(int j=i+1;j<=n-1;j++){
                // 섞으면 안되는 경우 제외
                if(isNotMix[i][j]){continue;}
                for(int k=j+1;k<=n;k++){
                    // 섞으면 안되는 경우 제외
                    if(isNotMix[i][k] | isNotMix[j][k]){continue;}
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
}