한윤정이 이탈리아에 가서 아이스크림을 사먹는데 성공다국어

한국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

8427

3353

2513

39.712%

문제

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

입력

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

출력

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

예제 입력 1 복사

예제 출력 1 복사

sollution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
 
int main()
{
    int N;
    int cant_combi_num;
    bool** cant_combi;
    bool*** al_cant_combi;
 
    std::cin >> N >> cant_combi_num;
 
    cant_combi = new bool* [200];
 
    for (int i = 0; i < 200; i++)
    {
        cant_combi[i] = new bool[200];
    }
 
    al_cant_combi = new bool** [200];
    for (int i = 0; i < 200; i++)
    {
        al_cant_combi[i] = new bool* [200];
        for (int j = 0; j < 200; j++)
        {
            al_cant_combi[i][j] = new bool[200];
            for (int k = 0; k < 200; k++)
            {
                al_cant_combi[i][j][k] = false;
            }
        }
    }
 
    for (int i = 0; i < 200; i++)
    {
        for (int j = 0; j < 200; j++)
        {
            cant_combi[i][j] = false;
        }
    }
 
    for (int i = 0; i < cant_combi_num; i++)
    {
        int scan1;
        int scan2;
        std::cin >> scan1 >> scan2;
        cant_combi[scan1 - 1][scan2 - 1] = true;
        cant_combi[scan2 - 1][scan1 - 1] = true;
    }
 
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                if (cant_combi[i][j] || cant_combi[j][k] || cant_combi[i][k] ||al_cant_combi[i][j][k])
                {
                    continue;
                }
                if (i == j || j == k || k == i)
                {
                    continue;
                }
                sum++;
                al_cant_combi[i][j][k] = true;
                al_cant_combi[i][k][j] = true;
                al_cant_combi[k][i][j] = true;
                al_cant_combi[k][j][i] = true;
                al_cant_combi[j][i][k] = true;
                al_cant_combi[j][k][i] = true;
            }
        }
    }
    std::cout << sum;
 
    for (int i = 0; i < 200; i++)
    {
        delete[]cant_combi[i];
        for (int j = 0; j < 200; j++)
        {
            delete[]al_cant_combi[i][j];
        }
        delete[]al_cant_combi[i];
    }
    delete[]cant_combi;
    delete[]al_cant_combi;
 
}
Colored by Color Scripter
cs

말그대로 진흙탕 싸움을 해서 푼 문제라 할 수 있다(...)

우선 안되는 조합을 2차원 bool 배열을 이용해 입력받는다.

근데 안되는 조합은 입력받은 2차원 bool 배열만이 아니다.

이미 출력한 조합도 안되는 조합 중 한 가지다.

문제를 풀다가 이것을 발견하고야 만 나는 3차원 bool 배열을 만들었다.

3차원 bool 배열에 이미 출력한 조합을 입력했다.

사실 고등학교 때 배운 확률과 통계를 이용하면 더 깔끔하게 풀 수 있는 문제이긴 하나

기억이 안나는 걸 어찌할 수는 없다.

그렇다고 다시 배우기는 귀찮고 말이다.

그러나 취업 전 공부해야 할 과목이 어째 하나 더 늘은 기분이다.