잘못 배달된 편지

배달부 Dan의 경력이 순조롭지 않다. 어제 그는 브르노에 있는 $N$채의 집 모두에 전기 요금 고지서를 전달해야 했다. 그런데 또다시 고지서 순서를 뒤섞어서, 대부분의 고지서를 엉뚱한 집에 전달해 버렸다. 그래도 그는 최소 한 장의 편지는 올바른 집에 전달했다고 확신한다. 그 편지를 찾아 줄 수 있겠는가?

브르노의 집들은 1번부터 $N$번까지 번호가 매겨져 있다. 고지서는 $N$장이며, 각각 서로 다른 집 앞으로 되어 있다. 모든 집은 고지서를 정확히 한 장씩 받았다. Dan은 아무 집이나 찾아가 초인종을 누르고, 그 집 주민에게 어느 집 앞으로 된 편지를 받았는지 물어볼 수 있다. Dan은 많은 사람을 방해하고 싶지 않아서, 확인하는 집의 수를 최소로 줄이려고 한다.

• $N = 1000$
• $T = 1000$
• 적어도 한 장의 편지는 올바른 집에 배달되었다.