https://www.acmicpc.net/problem/20529
20529번: 가장 가까운 세 사람의 심리적 거리
각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.
www.acmicpc.net
본 문제는 브루트포스 알고리즘과 비둘기집 원리를 이용해서 푸는 문제이다.
실버1인 이유는 비둘기집 원리에 대한 이해도가 있으면 바로 풀 수 있기 때문이다.
반대로 나는 비둘기집 원리를 까먹고있어서(2년전 이산구조때 배움) 왜 자꾸 틀리는지 모르고 있었다.
비둘기집 원리를 알고 있었으면 틀린 내 코드에 단 코드 두줄 추가로 문제를 맞출 수 있었다...
일단, 어떻게 풀었는지 설명해보겠다.
총 입력받은 개수들에 대해 조합을 이용하여 3개씩 묶어 가장 적은 심리적 거리를 위한 후보들을 만들었다.
이후, 해당 후보들을 반복문들 통해 3개씩 묶인 후보들을 2개씩 조합을 이용해 거리를 구하였다.
거리는 차집합을 통해 나오는 결과의 길이를 통해 구하였다.
마지막으로 min(r, res)를 통해 최소 심리적 거리를 업데이트하도록 하였다.

초반에 if n>32:print(0); continue를 해야하는 것을 안했기에 계속 시간초과 문제가 생겼었다.
왜 32보다 커야하나? MBTI는 총 경우의 수가 16개가 있다.
만약 들어오는 입력이 17개가 들어온다면, 17개중 2개씩 겹치는 MBTI가 최소 한개가 존재한다.
그리고 들어오는 입력이 33개가 된다면 33개중 3개씩 겹치게 되는 MBTI가 최소 한개가 존재할 수 있다.
32개까지 겹치는 MBTI가 2개씩 쌍지어졌다면, 33개부터는 3개씩 겹치게 되는 MBTI가 한개 존재할 수 있다는 비둘기집 원리를 이용한 것이다.
즉, n이 32보다 크면 겹치는 MBTI가 3개 존재하므로 그 3개의 거리가 0임을 바로 출력해주면 n이 매우 커지더라도 예외처리를 할 수 있으므로 시간초과 문제를 해결할 수 있는 것이다.

3중 for문 대신 비효율적이지만 좀 코드를 줄일 수 있도록 combination을 사용하여 숏코딩 순위권에 들 수 있었다.
개꿀~~

1일 1백준 31일째....
'백준에 대가리 깨지는중' 카테고리의 다른 글
[백준] 골드4 DSLR (3) | 2023.06.22 |
---|---|
[백준] 실버3 파도반 수열 (3) | 2023.06.09 |
[백준] 실버1 경로 찾기 (0) | 2023.06.06 |
[백준] 실버1 쉬운 최단거리 (0) | 2023.06.05 |
[백준] 실버3 조합 (0) | 2023.06.05 |