모든 조건을 함께 고려한 입력만 주어집니다.

이 글은 질문보다는 수정 요청글로 자주 보는 내용에 대한 매크로(?) 답변용입니다.

 

문제들 중에는 다음과 같은 조건을 가진 것이 많습니다. 입력으로 그래프가 주어지는데, 정점의 개수가 $1 \le N \le 100,000$개, 간선의 개수가 $1 \le M \le 200,000$개이고, 간선의 양 끝점은 서로 다르며 중복된 간선이 없다고 합니다. 그런데 여기서 의문이 듭니다. 정점의 개수가 1개 이상이라고 하는데, 정점이 1개이면 간선은 하나도 못 주어지지 않나요? 그렇다면 정점도 1개 이상이고 간선도 1개 이상이라는 조건이 잘못된 것 아닌가요?

 

하지만 조건은 이렇게 따로 따로 분리해놓고 생각해야 하는 것이 아닙니다. 다음과 같은 예시를 보겠습니다.

 

"입력으로 $1$ 이상 $1,000,000$ 이하의 정수 $N$이 주어진다. 단, $N$은 소수이다."

 

이 조건도 $N$이 1이나 100만이면 소수가 아닌데 이렇게 범위를 준 것이 잘못되었다고 생각되나요? 아마도 아닐 것입니다. 이 조건이 처음의 조건과 달리 틀리지 않게 느껴지는 이유는 두 번째 문장이 첫 번째 문장의 변수에 대한 직접적인 부가조건을 제시하고 있기 때문입니다. 그럼, 다음은 어떨까요?

 

"$1$ 이상 $1,000,000,000$ 이하의 정수 $N$이 주어진다. 답이 존재하는 경우만 입력으로 주어진다."

 

이 문제에서 $N=1$일 때 답이 존재하지 않는다면 이 조건은 틀렸을까요? 그렇게 생각하지는 않을 것입니다. 뒤쪽에서 답이 유일하게 결정되게 해준다고 했으니까, $N$의 범위가 얼마로 되어 있든 답이 존재하지 않는 것은 알아서 거르고 줄 것이라고 예상할 것입니다.

 

다시 처음의 조건으로 돌아가 봅시다. 이 조건도 마찬가지입니다. 비록 $N$의 범위는 1 이상이라고 했지만, 뒤쪽의 $M$의 조건은 $N$이 1이 될 수 없음을 간접적으로 보여주고 있습니다. 즉, 문제에서는 두 조건을 모두 만족하는 것만 입력으로 주면 될 뿐이고, $N$이 1인 것을 어떻게든 주어야만 하는 것이 아니기 때문에 조건이 틀렸다고 할 수 없습니다. 문제의 조건을 모두 고려했을 때 주어지는 것이 불가능한 입력은 그냥 주어지지 않으면 될 뿐이고, 변수의 범위부터 모조리 칼같이 설정하고 들어가야 하는 것이 아닙니다.

 

사실 $N$이 2 이상이라고 조건을 바꾼다고 해도, $N=2$, $M=100$인 입력은 존재할 수 없지만 이런 문제를 제기하는 사람은 없습니다. 따져보면, 앞의 이야기나 지금 이야기나 결국 $N$과 $M$이라는 두 개의 독립된 변수, 그리고 중복된 간선이 없다는 별도의 조건을 모두 고려했을 때 주어질 수 있는 것만 주어진다는 점에서 아무런 차이가 없는데도 그렇습니다. 그냥 실제로는 주어질 수 없는 수를 범위에 포함시킨 것이 어색하게 느껴졌을 뿐이며, 조건 자체로는 아무런 문제가 없기 때문에 수정을 할 필요가 없는 사항입니다.