[S4] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

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

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

흐흐... 하는 방법 아니까 엄청 쉽네..

내가 푼 방법으로는 너무 복잡하다.. 알게 된 방법으로 작성한 코드를 설명하겠다.

조합의 번호가 주어진다.

2차원 배열로 쉽게 해결이 가능하다.

주어진 예제를 표로 만들어 보겠다.

5 3
1 2
3 4
1 3

	1	2	3	4	5
1		X	X
2	X
3	X			X
4			X
5

주어진 예제는 다음과 같이 표시 가능하다.

자

1 -> 4 -> 5

1 -> 5 /

2 -> 3 -> 5

2 -> 4 -> 5

2 -> 5

3 -> 5

4 -> 5

가능한 방법은 1 -> 4 -> 5 / 2 -> 3 -> 5 / 2 -> 4 -> 5로 3가지 이다.

1에서 가능한 수들은 4와 5이다. 하지만 5로는 만들 수 없다. 다음 수가 없기 때문이다.(중복조합이기 때문에 크기순으로 가져간다 하자. 그러면 1 -> 5 다음 값은 존재하지 않는다.)

2를 살펴보면 2 -> 3 -> 5가 가능하다. 하지만 2 -> 3 -> 4가 가능하지 않는 이유는? 2 -> 3은 가능하지만 3 -> 4는 불가능 하다. 그리고 여기에서 2 -> 4는 가능한지도 살펴봐야 한다. 이러한 방식으로 count값을 늘려 count를 출력하면 된다.

#include <cstdio>

int main(void) {
    bool ice[201][201]{};
    int N, M; scanf("%d %d", &N, &M);
    int n1, n2;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &n1, &n2);
        ice[n1][n2] = true, ice[n2][n1] = true;
    }

    int count = 0;
    for (int i = 1; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (!ice[i][j]) {
                for (int k = j + 1; k <= N; k++) {
                    if (!ice[j][k] && !ice[i][k]) count++; 
                }
            }
        }
    }
    printf("%d", count);
}