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

 

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

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

 

처음엔 섞어 먹으면 안 되는 조합을 3중 for문안에 또 하나의 for문을 넣어서 했는데 역시,,, 시간 초과

3가지 아이스크림을 선택하는데, 두 개째 아이스크림을 선택했을 때 섞어먹으면 안 되는 조합을 먼저 체크 ch [i][j] == true

세 개째 아이스크림을 선택했을 때 또, 섞어먹으면 안되는 조합을 체크 ch [j][k] == true || ch [i][k] == true 

 

#include <iostream>
#include <vector>
using namespace std;
int n, m, cnt=0;
bool ch[205][205];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        ch[a][b] = ch[b][a] = true; //섞어먹으면 안되는 조합의 아이스크림 번호
    }
    
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            if(ch[i][j]) continue; //섞어 먹으면 안되는 조합
            for(int k=j+1; k<=n; k++){
                if(ch[i][k] || ch[j][k]) continue; //섞어 먹으면 안되는 조합
                ++cnt;
            }
        }
    }
    cout << cnt << '\n';
    return 0;
}