백준 18868 멀티버스Ⅰ Kotlin (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/18868

18868번: 멀티버스 Ⅰ

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

• 2 ≤ M ≤ 10
• 3 ≤ N ≤ 100
• 1 ≤ 행성의 크기 ≤ 10,000

알고리즘 분류

• 브루트포스 알고리즘

풀이

완전 탐색 문제이다.

오늘 있었던 쇼미더코드에 연습 문제로 있던 문제다.

음 딱히 설명할 게 없다.

4중 포문으로 완탐 돌리면 끝

아래 코드를 보면 쉽게 이해할 수 있을 것이다.

 

코드

val br = System.`in`.bufferedReader()
//m 우주 개수 2<=m<=10
//n 행성 개수 3<=n<=100
//서로 조건만 같으면 됨

lateinit var universe: Array<IntArray>

fun check(uni1: IntArray, uni2: IntArray, size: Int):Int{
    for(i in 0 until size){
        for(j in i+1 until size){
            //세 조건 중 하나만 일치하면 패스
            var isSame=false
            if((uni1[i]<uni1[j]) && (uni2[i]<uni2[j])){
                isSame=true
            }
            else if((uni1[i]>uni1[j]) && (uni2[i]>uni2[j])){
                isSame = true
            }
            else if((uni1[i]==uni1[j]) && (uni2[i]==uni2[j]) ){
                isSame = true
            }
            //세 조건 중 하나라도 만족하지 못하면 false
            if(!isSame) return 0
        }
    }
    return 1
}


fun main() = with(System.out.bufferedWriter()){

    val(n,m) = br.readLine().split(' ').map{it.toInt()}
    universe = Array(n){br.readLine().split(' ').map{it.toInt()}.toIntArray()}
    var answer=0


    //두 쌍
    for(i in 0 until n){
        for(j in i+1 until n){
            //유효성 검사
            answer += check(universe[i],universe[j],m)
        }
    }

    write("$answer")
    close()
}