[BOJ] 2215. 원형 네트워크

문제 링크

$N$개의 컴퓨터들이 원형으로 연결되어 있는데 이들 중 일부를 광섬유로 변결할 예정이고 이러한 요청이 $P$개가 있습니다. 이때, 최소한의 연결만으로 모든 요청을 만족하게 하려고 합니다.

요청 $p \, q$가 들어왔다고 해봅시다. 일반성을 잃지 않고 $p \leq q$라고 가정해보죠. 그럼 아래와 같이 두가지 방법으로 연결할 수 있습니다.

위 방법은 $0$, 아래 방법은 $1$로 표기해보도록 하겠습니다.

그럼 각 회선이 광섬유로 교체되지 않는 상태를 길이가 $P$인 문자열로 표현할 수 있습니다.
문제의 예제 1의 경우 다음과 같이 적을 수 있습니다.

실제로 각 상태값은 유일합니다. 다시말해 가장 많이 나오는 상태값의 갯수를 구해서 $N$에 빼서 나오는 값이 답이 됩니다. 방금 논리대로 예제 1의 답을 구하면 3이되고 실제 답이랑 일치하는것을 확인할 수 있습니다.

C++에서는 unordered_map, C#에서는 Dictionary를 사용하면 시간복잡도 $O(NP)$에 해결할 수 있습니다.