[BOJ][Python]20529 풀이

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

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

import sys
ssr = sys.stdin.readline

def cal_dist(stu_stack):
    result = 0
    for i in range(2, -1, -1):
        for j in range(4):
            tmp = 0
            if stu_stack[i][j] != stu_stack[i-1][j]:
                tmp += 1
            result += tmp
    return result

def f(start, stu_stack):
    if len(stu_stack) == 3:
        distance = cal_dist(stu_stack)
        ans.append(distance)
        return
    for i in range(start, n):
        if visited[i] == False:
            visited[i] = True
            stu_stack.append(students[i])
            f(i+1, stu_stack)
            visited[i] = False
            stu_stack.pop()

t = int(ssr())
for _ in range(t):
    n = int(ssr())
    students = ssr().strip().split()
    if n > 32:
        print(0)
    else:
        visited = [False for _ in range(n)]
        ans = []
        f(0, [])
        print(min(ans))

이번 문제는 새로 배우는 내용이 있어서 가져와봤습니다. '비둘기집 원리'라는 것인데요. 비둘기집 원리란 n+1개의 물건을 n개의 상자에 넣을 때 적어도 한 상자에는 두 개이상의 물건이 들어있다는 원리입니다. 원래 확률과 통계를 배우게 되면 해당 내용을 배우는 일이 있다고 합니다(고등학교 교과 과정에서 설명하는 일은 드물다고 하네요). 사실 내용을 보면 뭔 원리니 뭐니 하기보다 너무 당연한 일이 아닌가 하는 생각이 드는 내용입니다만, 굳이 이름을 붙인 건 이 원리가 적용되는 사례가 정말 많아서 지칭을 편하게 하기 위함이라는 글이 있었습니다(그래서 같은 원리임에도 다리클레의 방 나누기 원칙, 서랍 원리 등등의 다른 이름들로 부르는 경우도 있다고 하네요).

 

처음에는 최근에 어째 백트래킹 문제를 많이 풀게 되어서 생각나는게 백트래킹이라 그냥 그렇게 풀었는데 시간초과가 나더라구요. 그래서 코드 자체는 문제가 없으니까 질문을 좀 살펴봤더니 비둘기집 원리에 대해서 알아보라는 분이 있으셔서 찾아봤습니다. 위키피디아에서 설명만 읽어가지고는 여기에 어떻게 접목을 시킬지 잘 모르겠더라구요. 그래서 유튜브 강의도 좀 찾아보고 이런저런 용례도 찾아보니까 어느정도 감이 잡혔습니다.

 

결론부터 말하자면 해당 문제는 n이 32를 넘으면 답을 0을 출력하도록 하면 시간 초과가 나지 않습니다. 같은 mbti를 가진 사람이 3명 있다면 해당 케이스에서는 심리적 거리의 최솟값이 0이 나오겠죠. 그렇다면 최소한 3명이 같은 mbti를 갖는 경우는 언제일까요. 비둘기집의 원리니 뭐니 하는 건 솔직히 별로 중요하지도 않습니다. 최악의 경우를 한 번 생각해볼게요.

 

최대한 같은 사람이 많이 나와야 심리적 거리가 줄어들텐데 최악의 경우는 모두가 다 다른 mbti를 갖는 경우가 되겠죠. 16가지니까 16명일 때의 최악의 경우는 전부 mbti가 다른 경우일 겁니다. 그런데 거기서 1명만 더 들어와도 무조건 하나의 mbti는 중복되는 게 있을겁니다. 그럼 32명일 때의 최악의 경우는 뭘까요. 하나라도 같은게 3명이면 0이 될텐데 같은 mbti가 전부 2명씩 존재하는 겁니다. 그러면 여기서 뭐라도 하나가 더 들어오면 같은 mbti를 갖는게 3명이 되겠죠. 따라서 33명부터는 무조건 같은 mbti를 갖는 사람이 3명 존재하고, 심리적 거리는 0이 된다는 것입니다.

 

비둘기집 원리니 뭐니 처음 듣는 말로 괜히 현혹될 수 있지만 결국 여러분들이 평상시에 한 번쯤은 생각해 본적 있는 원리일 것입니다. 다만 이렇게 알고리즘 문제에 적용해볼 생각이 없다면 저처럼 약간 헤매셨을 수도 있을 것 같네요. 아무튼 그래도 새롭게 알게 되는게 있는 문제였습니다. 나쁘지 않았어요.