20529 가장 가까운 세 사람의 심리적 거리 / c++ / Silver1 / 1시간 24분
문제 및 코드
풀이 과정
완전 탐색 / 비둘기집 원리
- T개의 테스트 케이스 동안, N개의 MBTI가 주어질 때, 세 사람의 심리적 거리의 합의 최소값을 출력하는 문제.
(이 때 심리적 거리는, 두 MBTI 각 부분의 알파벳 차이의 합)
- 우선 이 문제를 풀기 위해 필요한 비둘기집 원리를 알아야 한다.
- N + 1 개의 물건을 N개의 상자에 넣을 때, 최소한 한 상자는 두 개 이상의 물건이 들어가 있다. 라는 원리이다.
- 이를 이 문제에 대입해보면 MBTI는 16개이다.
그렇다면 사람이 1~16명까지는 어떤 MBTI는 최소 1개 겹친다.
(상자 16개, 물건 1~16개, 물건 하나 이상 들어간 상자가 최소 1개)
또 사람이 17~32명이면 어떤 MBTI는 최소 2개 겹친다.
(상자 16개, 물건 17~32개, 물건 둘 이상 들어간 상자가 최소 1개)
마지막으로 사람이 33명 이상이면, 어떤 MBTI는 최소 3개 겹친다.
(상자 16개, 물견 33개, 물건 셋 이상 들어간 상자 최소 1개)
- 따라서 이 문제는 사람(N)이 33명 이상이 되면, 3명 이상인 MBTI가 생기므로 비교할 필요가 없이 답이 0이 된다.
- 32명 이하인 경우에는, 중복이 없는 조합으로 3명을 뽑아서 그 3명의 심리적 거리의 합을 구해 그 중 최소값을 완전 탐색으로 구하면 된다.
- 해결
회고
- 처음엔 백트래킹으로 3명을 뽑은 뒤 완전 탐색으로 최소값을 구하려고 하니, 한참을 최적화를 해봐도, 이 비둘기 집의 원리를 모르고서는 시간 안에 해결할 수 없었다.
- 1시간이 넘어서 질문 게시판을 찾아봤다. 그 때 비둘기 집의 원리를 알게 되었다.
- 나중에 알고 보니 이렇게 적은 수의 경우 (32 이하) 굳이 백트래킹을 쓸 필요도 없이 그냥 3중 루프를 돌리는게 훨씬 효율적이다.
- 또 나는 두 MBTI를 비교한 결과를 맵에 캐싱해뒀었는데, 그럴 필요가 전혀 없었다. 두 MBTI의 비교는 결국 4번의 문자 비교로 끝나기 때문에 오히려 맵을 두번 탐색하는게 (혹은 값을 채워넣는게) 훨씬 비효율적이었다.
- 알고리즘 문제를 많이 풀면서 이런 저런 알고리즘과 원리들을 봐왔지만, 이렇게 오늘도 또 한 원리를 배웠다. 비둘기 집의 원리 잘 기억해둬야겠다.
