백준 11389번 - 흑백 이미지

[문제설명]

먼저 2차원 배열 동적할당으로, 사용자가 입력한 값으로 A사각형과 B사각형 밝기 표를 만든다.

 

그리고, A사각형에서 B사각형 R x C 크기의 사각형 영역중에 비슷한 영역이 몇 개 인지를 세야한다.

 

" 어떤 실수 p와 q가 모든 1 ≤ i ≤ R, 1 ≤ j ≤ C에 대해 p·A[x + i - 1, y + j - 1] + q = B[i, j]를 만족시키면, A에서 선택한 직사각형과 사진 B는 비슷하다. "

 

-> (4-2+1)*(4-2+1) = 9개 중에서 공식을 통해 비슷한 영역은 5개인 것을 확인할 수 있다.

-> (5-3+1)*(5-3+1) = 9개 중에서, 테이블 B의 밝기 값이 똑같기 때문에 p = 0, q = 77일 때, 모든 직사각형에 대해 매칭이 된다. 

-> 9개가 비슷한 영역이다.

-----

[나의 문제정리]

1. 먼저, A 사각형과 B 사각형의 크기를 입력을 받고, 밝기를 2차원배열 동적할당으로 입력을 받아서 저장해둔다.

2. A 사각형에서 꼭지점 (x, y)를 B 사각형의 크기만큼 돌린다. (1 ≤ x ≤ N - R + 1, 1 ≤ y ≤ M - C + 1)

3. 도는 과정에서, 어떤 실수 p,q가 p × A[x + i - 1, y + j - 1] + q = B[i, j]를 만족하면 비슷한 영역이므로 비슷한 영역의 개수를 카운트 한다.

4. 비슷한 영역의 개수를 출력한다.

 

p와 q를 먼저 구해서, 모두 p × A[x + i - 1, y + j - 1] + q = B[i, j]를 만족하는지 확인하고, 만족하면 count값을 증가한다.

 

3번에서 공식을 만족한다는 의미는

px + q = y의 의미로서 (px - q - y)의 제곱이 = 0 이다는 말과 일맥상통하다.

그리고 한 직선상에 있다고 봐도 된다.

 

제 3회 kriiicon 문제 출제자가 제공한 힌트는 다음과 같았다. (무한 구글링으로 찾음)