PKU 1050. To the max. get AC -_-;;

main() { int iInnerCnt, iOuterCnt, iTempCnt, n, max; int matrix[101][101], temp[101]; scanf("%d", &n); max = 0; for (iOuterCnt = 1; iOuterCnt <= n; iOuterCnt++) { matrix[iOuterCnt][0] = 0; for (iInnerCnt = 1; iInnerCnt <= n; iInnerCnt++) { scanf("%d", &matrix[iOuterCnt][iInnerCnt]); if (matrix[iOuterCnt][iInnerCnt] > max) { max = matrix[iOuterCnt][iInnerCnt]; } matrix[iOuterCnt][iInnerCnt] += matrix[iOuterCnt][iInnerCnt - 1]; } } temp[0] = 0; for (iOuterCnt = 1; iOuterCnt <= n; iOuterCnt++) { for (iTempCnt = 0; iTempCnt < iOuterCnt; iTempCnt++) { for (iInnerCnt = 1; iInnerCnt <= n; iInnerCnt++) { temp[iInnerCnt] = matrix[iInnerCnt][iOuterCnt] - matrix[iInnerCnt][iTempCnt]; if (temp[iInnerCnt] < temp[iInnerCnt] + temp[iInnerCnt - 1]) { temp[iInnerCnt] = temp[iInnerCnt] + temp[iInnerCnt - 1]; } if (max < temp[iInnerCnt]) { max = temp[iInnerCnt]; } } } } printf("%d\n", max); return 0; } <SPAN id=tx_marker_caret></SPAN>

슙라;

이미 푼거였는데 합과곱에 정신팔려서

이미 푼 문제인지 모르고 제껴놓고 있었습니다.

-_-;

이거 그냥 돌리면 TL 그냥 걸립니다.

5 X 5 배열을 받는다고 가정할때,

(0, 0)부터 (0, 4)까진 그냥 받고,

(1, 0)부터 (1, 4)까진 (0, 0)부터 (0, 4)까지의 값을 각각 더해서 저장합니다.

그러니까, (1, 0)에는 (0, 0)의 원래 값과, (1, 0)에 입력받은 값이 더해진채로 저장되는 것이지요.

이후 (2, 1)부터 (4, 2)까지의 부분행렬 내의 값들 합을 구하고 싶다면,

(3, 2)와 (3, 0)을 빼고, (4, 2)에서 (4, 0)를 뺍니다. 또한 (2, 2)에서 (2, 0)을 빼구요.

이 값들은 각각 (3, 1)과 (3, 2)의 합, (4, 1)과 (4, 2)의 합, (2, 1)과 (2, 2)의 합이 되지요.

이 세 값의 합이 원하는 답이 되는겁니다.

간단하지요?