코드포스 2057A) Mex Table

 

Mex Table

 

코드포스에서 쉬운 문제중 하나인 Mex Table 이 문제는 풀기 쉬운편에 속한다. 일단 문제를 풀기 위해 MEX 함수에 대해 이해하는 시간을 가져보자. MEX 함수는 0을 포함한 음이 아닌 정수중 collection 에 나열되지 않은 가장 최솟값을 뜻한다. 예를 들면, 아래식은 반드시 0의 값을 가진다.

$$MEX(1,2,3,4)=0$$

이 값이 반드시 0을 가지는 이유는 0을 포함한 음이 아닌 정수이므로 0이 가장 작은 값이기때문이다. 이해가 안간다면, 검색을 해봐도 좋고, 문제를 다시 읽어봐도 좋다. 일단 MEX 는 이렇게 설명하고 넘어가겠다.

 

사실 문제에서 페이크인지 일부러 적어둔지는 모르겠지만, 사용할수 있는 가짓수를 정렬해서 값을 최대화 하는 것이라고 하는데 실상 이리저리 막해보면 결국 어떻게 배열하든 다 같은 값이 나온다. 여튼, 그렇게 값을 1*1, 1*2, 1*3, 2*1, 2*2, 2*3, 3*1, 3*2, 3*3 으로 배열하다보면 하나의 규칙이 보인다.

 

결국 0은 한번밖에 등장하지 못하므로 0을 포함시키지 못한 행과열은 모두 값이 0으로 수렴되게 되고, 그러면 최대화 시키기 위해서는 0이 있는 행 또는 열에서 가장 크게 나올수 있는 수인 (max(n, m)) 을 등장시킨다고 했을때, 그러면 다른 열 또는 행(만약 앞에서 행을 골랐다면 열)은 1을 가지게 된다.

 

즉, 그래서 결국 max(n, m) + 1 으로 식이 정리된다.

코드

n = int(input())
sizes = [list(map(int, input().split())) for _ in range(n)]

for size in sizes:
​​​​print(f'{max(size[0], size[1])}\n')