[BAEKJOON] 백준 18268: Cow Gymnastics (C#)

문제 링크

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

 

 

문제

In order to improve their physical fitness, the cows have taken up gymnastics! Farmer John designates his favorite cow Bessie to coach the N other cows and to assess their progress as they learn various gymnastic skills.

In each of K practice sessions (1≤K≤10), Bessie ranks the N cows according to their performance (1≤N≤20). Afterward, she is curious about the consistency in these rankings. A pair of two distinct cows is consistent if one cow did better than the other one in every practice session.

Help Bessie compute the total number of consistent pairs.

 

 

입력

The first line of the input file contains two positive integers K and N. The next K lines will each contain the integers 1…N in some order, indicating the rankings of the cows (cows are identified by the numbers 1…N). If A appears before B in one of these lines, that means cow A did better than cow B.

 

 

출력

Output, on a single line, the number of consistent pairs.

 

 

 

통과한 답안

namespace _18268
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int K = int.Parse(inputs[0]);
            int N = int.Parse(inputs[1]);

            int[][] rankings = new int[K][];
            for (int i = 0; i < K; i++)
            {
                rankings[i] = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            }

            int pairs = 0;

            for (int cow1 = 1; cow1 <= N; cow1++)
            {
                for (int cow2 = cow1 + 1; cow2 <= N; cow2++)
                {
                    bool cow1AlwaysBefore = true;
                    bool cow2AlwaysBefore = true;

                    for (int i = 0; i < K; i++)
                    {
                        int cow1Rank = Array.IndexOf(rankings[i], cow1);
                        int cow2Rank = Array.IndexOf(rankings[i], cow2);

                        if (cow1Rank > cow2Rank)
                        {
                            cow1AlwaysBefore = false;
                        }
                        if (cow1Rank < cow2Rank)
                        {
                            cow2AlwaysBefore = false;
                        }

                        if (!cow1AlwaysBefore && !cow2AlwaysBefore)
                        {
                            break;
                        }
                    }

                    if (cow1AlwaysBefore || cow2AlwaysBefore)
                    {
                        pairs++;
                    }
                }
            }

            Console.WriteLine(pairs);
        }
    }
}

 

N마리의 소들을 1위부터 N위까지 순위를 매긴 등수표가 K개 있을 때,

각각의 소들의 순위관계가 일정한 관계를 유지하는 페어의 수를 구하는 문제이다.

 

예제를 살펴보면

3 4

4 1 2 3

4 1 3 2

4 2 1 3

으로 4마리의 소가 3개의 등수표를 갖고 있을 때,

항상 같은 순위관계를 유지하는 것은

4와 1(항상 4가 1보다 높은 순위)

4와 2(항상 4가 2보다 높은 순위)

4와 3(항상 4가 3보다 높은 순위)

1과 3(항상 1이 3보다 높은 순위)

로 4개의 페어를 갖는다.

(1과 2의 경우에는 첫번째와 두번째는 1이 높지만 세번째는 2가 높아서 관계가 달라진다)

 

따라서 문제를 해결하기 위해서는 모든 입력값을 받은 뒤에

모든 경우에 대해서 cow1과 cow2가 모든 등수표에서 같은 관계인지 확인하면 된다.

이를 위해서 2개의 bool값을 선언한 뒤에 cow1이 항상 높은 순위인지

cow2가 항상 높은 순위인지 판단할 수 있도록 구현하였다.