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

문제 설명

이번 문제는 mbti가 주어졌을 때 네 가지 척도에서 다른 것의 개수를 심리적인 거리로 측정할 때, N명의 학생 중 가장 가까운 심리적 거리를 가지고 있는 3 학생의 심리적 거리를 구하는 문제입니다.

 

문제 풀이

아이디어

경우의 수

• 비교할 세 사람의 mbti가 모두 같은 경우
• 비교할 세 사람 중 두 사람의 mbti가 같은 경우
• 비교할 세 사람의 mbti가 모두 다를 경우

가장 가까운 거리를 가지는 조건

모두 같은 mbti를 가진 사람이 3명이면 3명의 심리적 거리는 0이 되므로, 같은 mbti를 가진 사람이 3명이 있는 경우 최소 심리적 거리는 0이 됩니다.

 

같은 mbti를 가진 사람이 2명이면 2명의 심리적 거리는 0입니다. 다른 한 사람과의 심리적거리를 a라 할 경우 3명의 심리적 거리는 2*a가 됩니다. 이는 세 사람의 mbti가 모두 같은 경우인 0보다는 크지만 가장 가까운 심리조건이 될 수 있는 경우 중 하나입니다.

 

같은 mbti를 가진 사람이 없는 3명이라면, 각각의 심리적 거리를 다 더해줘야 합니다.

mbti가 모두 다 다른 조건이라고 해서 가장 가까운 심리적 거리를 나타낼 수 없는 것은 아닙니다.

 

예) ISTJ, ISTP, ISFJ이 세 사람의 심리적 거리는 4로 두 명이 같은 mbti를 가지고 있는 ISTJ, ISTJ, INFP의 심리적 거리 6보다 심리적 거리가 작습니다.

 

풀이 

세 사람이 같은 mbti를 가지는 경우

mbti의 개수를 세 줄 dict를 선언한 뒤, 각 mbti의 개수를 세 줍니다.

mbti의 개수가 3개 이상이 되는 경우 이 mbti를 가진 세 명의 심리적 거리가 가장 가까우므로 답은 0이 됩니다.

 

두 사람이 같은 mbti를 가지는 경우

mbti의 개수를 세는 dict에서 mbti의 개수가 2개인 경우를 살펴봅니다.

같은 mbti를 가진 두 사람과 해당 mbti를 제외한 다른 사람들과의 심리적 거리를 계산해 비교해줍니다.

 

모두 다른 mbti를 가지는 경우

모두의 mbti가 다른 경우도 최소 심리거리를 나타낼 수 있으므로 살펴봅니다.

주어진 mbti를 각각 다른 mbti 세 개를 뽑아 심리적 거리를 비교해줍니다.

 

 

해결

이번 문제는 mbti가 같은 사람을 몇 명 비교할 것인지를 생각해내어 비교적 쉽게 풀 수 있었습니다.

 

문제 링크 : https://www.acmicpc.net/problem/20529

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

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/20529.py