https://www.acmicpc.net/problem/20529
20529번: 가장 가까운 세 사람의 심리적 거리
각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.
www.acmicpc.net
문제가 처음 봤을때는 하나하나 비교하면 못해도 시간복잡도가 O(N^3)이라 시간초과에 걸릴 것이 딱 보였다. 하지만 문제 태그를 보니 비둘기집의 원리가 있는걸 보고 MBTI는 16개 밖에 없으니 사람이 33명 이상이라면 못해도 3명은 같은 MBTI라 심리적 거리가 0이 되는 경우가 있다는 걸 알게 되었다.
그러므로 N이 32 이하 일때만 무식하게 브루트포스로 구하고 그 33 이상이라면 그냥 0을 출력하게 만들었다.
import sys
input = sys.stdin.readline
T=int(input().rstrip())
for _ in range(T):
N=int(input().rstrip())
l=(input().rstrip()).split()
if N>32:
print(0)
else:
mi=10
for i in range(N):
for j in range(N):
for k in range(N):
if i==j or j==k or k==i:
continue
cnt=0
a,b,c=l[i],l[j],l[k]
for v in range(4):
if a[v]!=b[v]:
cnt+=1
if b[v]!=c[v]:
cnt+=1
if c[v]!=a[v]:
cnt+=1
if mi>cnt:
mi=cnt
print(mi)
'문제해결(PS) > 백준(BOJ)' 카테고리의 다른 글
백준 11053 가장 긴 증가하는 부분 수열 (0) | 2024.12.25 |
---|---|
백준 15654 N과 M (5) (0) | 2024.12.22 |
백준 16928 뱀과 사다리 게임 (1) | 2024.05.01 |
백준 5525번 IOIOI 파이썬 (1) | 2024.04.18 |
백준 6064번 카잉달력 파이썬 (0) | 2024.04.13 |