[Baekjoon] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (for문 사용)

👀 문제 설명

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

5 3

1 2

3 4

1 3

 

예제 출력 1

3

 

✍🏻풀이

조합을 이용하는 문제이다.

 

c++에는 algorithm헤더에 순열을 구하는 next_permutation()이라는 함수가 있는데, 이 함수를 이용해서 조합을 구할 수 있다.

아래의 두 링크에 설명이 잘 되어있다.

next_permutation 함수를 사용해서 순열을 구하는 방법

next_permutation 함수를 사용해서 조합을 구하는 방법

 

처음에는 next_permutation 함수를 사용해 조합을 구하여 v 벡터에 넣고(do-while문이 반복될 때마다 v 벡터는 초기화된다)

v 벡터를 사용해 문제를 풀었다. 섞일 수 없는 아이스크림의 쌍은 vector<pair<int, int>> cantMix에 저장해뒀고, 매 조합마다 섞일 수 없는 아이스크림들이 v벡터에 속하는지 find 함수를 통해 찾으려 했다.

하지만 이렇게 푸니까 시간 초과가 떴는데, 추측하기로는 조합을 구하면서 최대 8,000,000 번을 수행하고, cantMix 벡터까지 for문으로 접근하니까 시간 초과가 나는 것 같다.

-> next_permutation은 N이 20만 넘어가도 터질 위험에 처한다! (시간복잡도가 크기 때문)

-> next_permutation은 10 언저리일 때 쓰면 좋다. [출처]

 

그래서 섞일 수 없는 아이스크림 조합을 int cantMix[205][205] 배열을 사용해 저장해두고, 이것을 사용했다.

예를 들어, 1번과 2번 아이스크림이 섞일 수 없는 조합이면, cantMix[1][2]와 cantMix[2][1]의 값을 1로 바꾼다.

매 조합마다 cantMix[x][y]값을 확인하면 된다.

 

next_permutation 사용 (Time-out)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    vector<pair<int, int>> cantMix;
    
    // input
    cin >> N >> M;
    for (int i = 0; i < M ; i++) {
        int first, second;

        cin >> first >> second;
        cantMix.push_back({ first, second }); // 섞으면 안되는 조합의 번호쌍을 저장하는 벡터 (1, 2) (3, 4) (1, 3) 저장
    }
    
    // getAnswer
    vector<int> v;
    for (int i = 1; i <= N; i++) {
        v.push_back(i);
    }
    
    // 조합 구하기
    vector<int> intd;
    for (int i = 0; i < 3; i++) {
        intd.push_back(1);
    }
    for (int i = 0; i < N - 3; i++) {
        intd.push_back(0);
    }
    
    sort(intd.begin(), intd.end());
    
    int answer = 0;
    do {
        vector<int> combiV;
        
        for (int i = 0; i < intd.size(); i++) {
            if (intd.at(i) == 1) {
                combiV.push_back(v.at(i));
            }
        }
        // -- combiV에는 조합의 경우가 들어간다.
        
        bool canCombi = true;
        for (int i = 0; i < cantMix.size(); i++) {
            int first = cantMix.at(i).first;
            int second = cantMix.at(i).second;
            
            if ((find(combiV.begin(), combiV.end(), first) != combiV.end()) && (find(combiV.begin(), combiV.end(), second) != combiV.end())) {
                canCombi = false; // 조합 불가능
                break;
            }
        }
        
        if (canCombi)
            answer++;
    } while(next_permutation(intd.begin(), intd.end()));
    
    cout << answer << endl;
    
    return 0;
}

 

정답 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int cantMix[205][205];

int main() {
    int N, M;
    int answer = 0;
    
    // input
    cin >> N >> M;
    for (int i = 0; i < M ; i++) {
        int first, second;

        cin >> first >> second;
        cantMix[first][second] = 1;
        cantMix[second][first] = 1;
    }
    
    // 조합 구하기
    for (int x = 1; x <= N - 2; x++) { // 조합의 첫번째 수는 N - 2 인덱스까지 가능
        for (int y = x + 1; y <= N - 1; y++) {
            if (cantMix[x][y] == 1) // x와 y가 조합이 불가능하면 다음으로 넘긴다
                continue;
            
            for (int z = y + 1; z <= N; z++) {
                if (cantMix[x][z] == 1 || cantMix[y][z] == 1)
                    continue;
                
                answer++;
            }
        }
    }
    
    cout << answer << endl;
    
    return 0;
}