[hackerrank] Largest Pyramid

문제 : https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid/problem

---

int arr[351][351]; //arr[i][j] : (i,j) 요소 값. (입력값)
int max_down[400][351][351] = {0}; //max_down[size][i][j] : j열의 arr[i][j] 부터 arr[i+size-1][j] 중 최대 값
int max_right[400][351][351] = {0}; //max_right[size][i][j] : i행의 arr[i][j] 부터 arr[i][j+size-1] 중 최대 값
int sum[351][351] = {0}; //sum[i][j] : (1,1) ~ (i,j) 까지의 직사각형에 속하는 배열 요소들의 합
int pyramid[400] = {0}; //pyramid[i] : 피라미드 크기가 i일 때 피라미드의 합

[그림 1]

max_right[4][i][j]는 [그림 1]에서 (i,j)에서 (i, j+4-1)까지 arr배열의 값 중 최대 값을 저장한다.

max_down[4][i][j]는 [그림 1]에서 (i,j)에서 (i+4-1, j)까지 arr배열 값 중 최대 값을 저장한다.

[그림 2]

sum[i][j] = arr[1][1~j] + arr[2][1~j] + … + arr[i][1~j]

= sum[i-1][j](2) + sum[i][j-1](3) - sum[i-1][j-1](1) + arr[i][j](4)

[그림 3]

(cx, cy)를 중심으로 크기가 2인 피라미드 범위는 [그림 3]의 어두운 부분이고 이는

빨간색부분 - 파란색 부분 2개 + 초록색 부분이다. (A합집합B = A + B - A교집합B)

이를 sum 배열을 이용해서 구할 수 있다.

[그림 4]

파란색 피라미드 부분에서는 2때문에 피라미드를 만들 수 없는 경우다.

하지만 빨간색 피라미드 부분에서는 조각을 추가하여 미라미드를 생성할 수 있다.

 

따라서 (cx, cy)를 피라미드의 중간 지점으로 보고 피라미드 크기를 키워가면서 피라미드를 만들 수 있는지 체크할 때 만들 수 없다고 반복문을 중지하면 안되고 확인할 수 있는 부분까지는 다 확인해봐야 한다.

 

피라미드를 만들 수 있는지는 피라미드 크기(size)를 1씩 증가시키면서 추가되는 테두리 부분에서의 최대값을 max_right, max_down 배열을 이용해서 구한다. 그리고 찾은 최대값(tmp)과 이전에 반복해서 찾은 tmp 값들 중 최대값을 current_maximum이라고 하면 current_maximum + (size-1)가 size보다 작거나 같으면 만들 수 있는 경우다.

즉, [그림 4]에서 size가 1일 때 tmp=1(1+(1-1))이고 current_maximum은 1이다. 이는 1보다 작거나 같은 값이므로 피라미드를 만들 수 있다.

size가 2일 때(파란색), tmp = 3(2+(2-1))이고 current_maximum은 3이다. 이는 2보다 크니까 피라미드를 만들 수 없는 경우다.

size가 3일 때(빨간색), tmp = 3(1+(3-1))이고 current_maximum은 3이다. 이는 3보다 작거나 같은 값이므로 피라미드를 만들 수 있는 경우다.

왜 current_maximum이랑 size를 비교하냐면 만약 [그림 4]에서 배열의 중앙 값이 1이 아닌 4라고 하자 그러면 size가 3일 때(빨간색), current_maximum은 3이 아닌 4가 되고, 3보다 큰 수이므로 이 경우는 피라미드를 만들 수 없는 경우다. 따라서 가장자리 크기만 비교하지 않고 피라미드 범위 안에 있는 모든 수를 이용해서 피라미드를 만들 수 있는지를 체크해야 하므로 current_maximum을 저장해가야 한다.

 

 

피라미드를 만들 수 있는 경우 해당 범위 안에 있는 arr배열 값들의 합을 sum배열을 이용해서 구하면 피라미드를 만드는데 추가해야하는 조각 수를 pyramid[size] - 합로 구할 수 있다. 만약 이가 k보다 작거나 같으면 조각을 추가해서 만들 수 있는 경우고, k보다 크면 피라미드를 만들 수 없을 뿐만 아니라 (cx, cy)를 중심으로 구하는 피라미드는 만들 수 없으므로(size는 1씩 커지고 범위가 커질수록 필요한 조각수는 더 많아지므로) 이 경우는 반복문을 중지하고 다음 (cx, cy)를 중심으로 피라미드 크기를 1부터 다시 탐색하기 시작한다.

 

피라미드를 만들 수 있는 경우 피라미드 크기가 이때까지 구한 정답보다 크다면 정답을 갱신한다.

 

(cx, cy)를 모든 arr배열(NxM)에서 탐색하고 그 지점에서 만들 수 있는 최대 크기의 피라미드까지 앞에서 설명한 알고리즘을 이용해서 만들 수 있는 최대 크기를 찾아낸다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/hackerrank/medium/Largest%20Pyramid.cpp

---

너무 어려워서 Editorial과 다른 사람의 소스코드를 분석해서 알아냈다.

알고나니 재밌는 문제