백준 2142 정돈된 배열

문제

https://www.acmicpc.net/problem/2142

2142번: 정돈된 배열

 

아이디어

문제가 시키는대로 한다면 O(N^4)일 것이고 이는 시간초과일 것입니다.

문제에서 주어진 식은 빨간건 빨간 것 끼리 파란건 파란 것 끼리 더하란 것입니다.

일단 저기서 알 수 있는건 i == k 또는 j == l이라면 좌변과 우변이 시행하는것이 같으므로 굳이 알아볼 필욘 없단 것입니다.

딱봐도 더러워보이는데 이럴경우, 좌변과 우변에 서로 공통된걸 몰아주면 될 것 같습니다.

아무튼 부등식을 어떻게 계산하기 편리하게 만들 것인가를 고민해봅시다.

y좌표가 같다거나, x좌표가 같다거나.. 아무튼 항들을 서로 옮기다보면 편리한 형대가 될 것입니다.

그렇게 해서

A[i][j] - A[i][l] <= A[k][j] - A[k][l]

란 꼴을 만들었습니다.

이는 x좌표 j,l(j<=l)선택했을 때, 두 y좌표 i,k가 i<=k이므로 y가 작은 두 점의 차는 y가 큰 두 점의 차보다 작아야한단 것입니다.

(A[i][j] - A[i][l] <= A[k][j] - A[k][l] (k = i+1,i+2,...,N))

i가 0일때 k가 1~N이 옵니다. 애초에 같은건 볼 필요가 없습니다.)

i가 1일때 k는 2~N이 옵니다.

i가 2일때 k는 3~N이 옵니다.

...

i가 N-1일때 k는 N이 옵니다.

즉 다음과 같은 관계가 성립합니다.

A[0][j] - A[0][l] <= A[1][j] - A[1][l] <= A[2][j] - A[2][l] <= A[3][j] - A[3][l] <= ... <= A[N-1][j] - A[N-1][l]

따라서 우린

어떤 y값에 대해 y+1과 비교만 하면 됩니다. 가능한 범위의 j,l에 대해서만 알아보면됩니다.

그렇게 O(N^3)에 해결이 가능합니다.

만약 성립하지 않은 것이 하나라도 있다면 실패합니다.

모든 y값에 대해 성립한다면 성공입니다.

 

풀이

#의사코드
function solve(){
	for (y:0;y < N-1;y++){
		for (j:0;j<=M-1;j++){
			for (l:j+1,j<=M-1;j++){
        		left = A[y][j] - A[y][l]
            	right = A[y+1][j] - A[y+1][l]
            	if left > right: return 'NO'
			}
		}
	}
	return 'YES'
}