[BOJ 18268] Cow Gymnastics

2021년 6월 9일

문제는 여기서 풀 수 있습니다.

문제 요약

$N$ 마리의 소들이 체조 연습을 시작했습니다. $K$ 번의 연습 세션이 진행되는 동안 각 연습 세션마다 다양한 평가를 통해 소들의 순위를 매깁니다. 모든 연습 세션에서 소 $A$ 가 소 $B$ 보다 순위가 높다면 두 마리의 소 ( $A$ , $B$ )는 일관된 쌍이라고 합니다. 일관된 쌍은 총 몇 쌍이 있는지 구하는 문제입니다.

문제 풀이

$N$ 과 $K$ 가 크지 않기 때문에 완전 탐색으로 풀 수 있습니다. 이 문제는 코드를 얼마나 체계적으로 작성할 수 있는지 확인할 수 있는 문제라 생각합니다. 최대한 독립적인 작업을 함수로 분리해 작성했습니다. 시간 복잡도는 $O(KN^3)$ 입니다.

#include <stdio.h>

int n, k, rank[11][21];

int getRank(int session, int target) {
    for (int i = 0; i < n; ++i) {
        if (rank[session][i] == target) {
            return i;
        }
    }
    return -1;
}

bool isConsistentPair(int a, int b) {
    for (int session = 0; session < k; ++session) {
        if (getRank(session, a) >= getRank(session, b)) {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &k, &n);
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &rank[i][j]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (isConsistentPair(i, j)) {
                ++ans;
            }
        }
    }

    printf("%d\n", ans);
}