https://www.acmicpc.net/problem/17089
문제요약
- 서로간에 친구인 A,B,C를 고르고, 친구수의 합을 구함(서로는 친구수에서 뺌 즉 -6)
- 최소값 구하기
접근법
- A,B,C 완전탐색을 하면 4000 3999 3998개
- 간선을 선택하는 경우에도 마찬가지
- 간선하나를 정하고(a-b 간선, M개) 간선에 포함되지 않는 점을 순회하면서(c, N개) a-c, b-c가 간선인지 확인하는 방법으로 세 친구를 완전탐색함
더 빠른 방법(다른 사람 코드, 풀이 참고)
- A, B, C를 구해나가는데, A < B, B < C인 관계만 선정해나감
- A의 친구이면서 A < B를 만족하는 B를 고르고
- B의 친구이면서 B < C를 만족하는 C를 고르고
- C가 A의 친구인지 판단하는 방식
newbieski