[6개월 안에 백준 플래티넘 달성하기] 7. 가장 가까운 세 사람의 심리적 거리 20529 | 백준 골드 달성 | 코틀린

2023. 10. 1 ~ 2023. 11. 09  골드 달성

 

실버 1 문제들을 풀기 시작하면서 슬슬 저의 멘탈을 힘들게 하는 문제들을 마주하게 되는 거 같습니다.

많이 접해보지 못한 알고리즘 유형이거나 수학적 지식이 필요한 문제일수록 풀기 어려워지는데 해당 문제도 이러한 이유로 풀지 못하고 결국 해설을 보고 풀게 되었습니다.

 

가장 가까운 세 사람의 심리적 거리

 

문제

 

풀이

개인적으로 해당 문제는 알고리즘에 대한 이해보다 수학적 센스가 있어야 풀 수 있다고 생각합니다. 그런 의미에서 못 풀었다는 거에 좀 더 좌절감을 느끼게 되었던 거 같습니다.

 

가장 기본적으로 생각나는 풀이법은 N개의 mbti를 모두 비교해 보는 것입니다.

그렇게 되면 복잡도는 N * (N-1) * (N-2) * 4 = N^3 가 되는데 N의 범위가 최대 100000인 점에서 시간제한에 걸릴 수밖에 없습니다.

 

처음에는 우선순위 큐를 이용해서 최대한 복잡도를 줄이고자 하였지만 여전히 시간초과가 났으며, 

그다음으로는 N^3을 N^2로 줄일 수 있는 방법을 찾고자 하였지만 존재하지 않았습니다.

 

어떻게든 복잡도를 줄이려고 했지만 사실 이 문제풀이의 복잡도는 N^3 이 맞았습니다. 그 대신 N의 범위가 16*16 보다 같거나 작은 수일 경우에만 N^3이며 그 외에는 1의 복잡도가 됩니다.

그 이유는 N이 16*16 보다 클 경우에는 답이 0밖에 나오지 않기 때문에 입니다.

 

이를 이해하기 위해

먼저 세 사람이 아닌 두 사람의 최소한의 심리적인 거리를 구한다고 해보겠습니다.

이때 최대한 심리적인 거리가 0이 되지 않도록 하겠습니다. (즉 MBTI가 겹치지 않도록 하겠습니다)

 

N = 3 ISTP, ISTJ, ISFJ

N = 4 ISTP, ISTJ, ISFJ, INTP

N = 5 ISTP, ISTJ, ISFJ, INTP, INFJ

      .

      .

      .

N = 16 ISTP, ISTJ, ISFJ, INTP, INFJ..., ENFP, ENFJ 

 

N이 16이 되는 순간 모든 MBTI 유형이 들어오게 됩니다.

그 말은 즉 N이 17이 되는 순간 중복되는 MBTI 유형이 적어도 하나는 생긴다는 소리가 됩니다.

결과적으로 두 사람이 있을 때 N > 16 이면 심리적 거리 = 0 이 되는 것입니다.

 

이와 마찬가지로 세 사람일 경우에도 똑같이 적용시키면 경우의 수가 16*16이 되며 N > 16*16 이 되면 심리적 거리 = 0 이 됩니다.

 

코드는 다음과 같습니다

fun main() = with(System.`in`.bufferedReader()) {

    // mbti 거리재는 메서드
    fun dist(s1: String, s2: String): Int{
        var count = 0
        for (i in 0 until 4) {
            if (s1[i] != s2[i]) count++
        }
        return count
    }

    var t = readLine().toInt()
    while (t-- > 0) {
        val n = readLine().toInt()
        val mbti = readLine().split(" ")
        
        // 무조건 같은 MBTI가 3개가 생기는 경우
        if (n > 16*16) {
            println(0)
            continue
        }

        var min = Int.MAX_VALUE
        for (i in 0..<n-2) {
            for (j in i+1..<n-1) {
                for (l in j + 1..<n) {
                    min = Math.min(min, dist(mbti[i], mbti[j]) + dist(mbti[i], mbti[l]) + dist(mbti[j], mbti[l]))
                }
            }
        }
        println(min)
    }
}

 

 

뭔가 당연한 듯하면서 이해가 잘 되지 않았던 문제인 거 같습니다.