어느 온천에는 $n$개의 방이 있는데 각 방에 인원 제한은 없다고 한다. 각 방에는 남자와 여자가 동시에 들어갈 수는 없으며, 남자들은 서로 모르는 남자들하고만 같은 방을 쓰고자 하고, 여자들은 서로 아는 여자들하고만 같은 방을 쓰고자 한다. $k$쌍의 부부가 온천에 함께 가서 방에 규칙에 맞게 들어갈 수 있을 최대의 수 $k$를 구하여라. 단 남편끼리 서로 알면 부인끼리도 서로 알며 반대로 부인끼리 서로 알면 남편끼리도 서로 안다.