[더블릿 - 15] 구슬 찾기/bead

프로그램 명: bead

제한시간: 1 초

모양은 같으나, 무게가 모두 다른 N 개의 구슬이 있다. N 은 홀수이며, 구슬에는 번호가 1..N 으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 M 개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운 가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N = 5이고, M = 4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번이 구슬 1번 보다 무겁다.
2. 구슬 4번이 구슬 3번 보다 무겁다.
3. 구슬 5번이 구슬 1번 보다 무겁다.
4. 구슬 4번이 구슬 2번 보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 자료의 첫 줄은 구슬의 개수를 나타내는 정수 N (1<=N<=99) 과 저울에 올려 본 쌍의 개수 M 이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력 형식

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력한다.

입출력 예

입력

5 4
2 1
4 3
5 1
4 2

출력

2

출처: 제20회한국정보올림피아드(2003.7.19) 중등부문제1

이 문제 또한 그래프의 도달가능성을 묻는 문제이다.

이전 문제에서 코드를 약간만 변경하면 된다.

Warshall 알고리즘을 사용하면 된다.

이전 문제 (키 순서 / koi_stature)

에서 nMax값과 adj_count() 함수만 약간 바꾸면 된다.

한 노드에 대해서 나보다 무거운게 (n + 1)/2개 이상 혹은 가벼운게 (n + 1)/2개 이상이어야한다.

무거운게 (n + 1)/2개이거나 가벼운것이 (n + 1)/2개면

이건 확실히 중간이 아니다.

P.S.

사실 이렇게 하면 틀려야한다.

근데 채점 데이터가 9개 밖에 안된다.

아마 채점 데이터를 보강하면 wrong answer가 뜰것이다.

이 코드에서 n이 짝수 일 때,

중간 무게인 것도 포함 될 수 있기 때문이다.

xCt 가 나보다 가벼운 구슬의 개수

yCt 가 나보다 무거운 구슬의 개수

를 나타내는데

n이 짝수일 때, ex... n = 4

nV = (4 + 1)/2 =  2

xCt >= nV가 참이라면

구슬 무게가 중간이 아니지만

(나보다 가벼운게 2개이상이면 이 구슬은 3번째 4번째)

yCt >= nV가 참이라면

구슬 무게가 중간일 수도 있기 때문이다.

(나보다 무거운게 2개이상이면 이 구슬은 1번째 2번째)

즉, 2번째가 될 수 있으므로

항상 참인 결과를 내지 않는다.

#include <iostream>

using namespace std;

  

const int nMax = 100;

int n, m, a, b;

int nV, ct;

int ar[nMax][nMax];

  

void adj();

void adj_count();

  

int main()

{

    cin >> n >> m;

    nV = (n + 1)/2;

  

    int i;

    for (i = 0; i < m; ++i)

    {

        cin >> a >> b;

        ar[a][b] = 1;

    }

  

    adj();

    adj_count();

  

    cout << ct << endl;

  

    return 0;

}

  

void adj()

{

    int i, j, k;

  

    for (k = 0; k < n; ++k)

        for (i = 1; i <=n; ++i)

            for (j = 1; j <=n; ++j)

                ar[i][j] = ar[i][j] | (ar[i][k + 1] & ar[k + 1][j]);

}

  

void adj_count()

{

    int i, j, xCt, yCt;

  

    for (i = 1; i <= n; ++i)

    {

        xCt = yCt = 0;

        for (j = 1; j <=n; ++j)

        {

            if (i != j)

            {

                if (ar[i][j]) xCt++;

                if (ar[j][i]) yCt++;

            }

        }

        if ( (xCt >= nV) | (yCt >= nV) )

            ct++;

    }

}