백준 2142번: 정돈된 배열

문제는 아주 심플하다.

N * M짜리 배열에서, 1≤i<k≤M, 1≤j<l≤N를 만족하는 모든 i, j, k, l에 대해서 A[i][j]+A[k][l]≤A[i][l]+A[k][j]가 성립하는지를 판별하는 문제이다. 문제에서도 그렇고 이 글에서도 편의상 1-index를 쓸 것이다.

 

대충 모든 경우에 대해 다 확인해보는 데에는 $O(n^2 m^2)$의 시간이 걸릴 것이라는 것을 잘 알 수 있다.

어떻게 줄일 수 있을까?

 

등식을 잘 관찰하면 특이한 성질을 확인할 수 있는데, 일종의 귀납적 성질이다.

 

j와 l의 차이가 2보다 클 때, 1≤i<k≤M, 1≤j<p<l≤N인 p에 대해 생각해보자.

A[i][j]+A[k][p]≤A[i][p]+A[k][j]

A[i][p]+A[k][l]≤A[i][l]+A[k][p]

만약 두 등식이 성립한다면, 양변을 더한 뒤 정리하면

A[i][j]+A[k][l]≤A[i][l]+A[k][j]이 성립한다.

 

다시 말해, 아래 그림에서

작은 네모 각각에 대해 위 등식이 성립한다면, 큰 하나의 네모에 대해서도 등식이 성립하는 것이다.

따라서, 모든 (i, j)와 (i + 1, j + 1) 쌍에 대해서만 위 등식이 성립하는지 확인하는 것으로 문제를 풀기 충분하다.

 

 

2142.cpp