백준 11660번

백준 11660번(구간 합 구하기 5)

시험 기간으로 잠시 알고리즘을 쉬었다. 3학년 정말 너무 바빠서 병행하기 너무 힘들어 학업에 좀 더 집중을 하였다. 그에 맞는 결과가 나올지는 모르겠지만..ㅎㅎ 간만에 알고리즘을 풀었는데 쉽지 않았다.

접근

처음에는 단순히 그냥 for문을 이용해서 연산을 해주려하였다. 하지만 사실 속으로는 당연히 M가지의 경우마다 매번 구간에 맞춰서 이중 for문 사실상 3중for문이 돌아가기에 시간초과가 뜰 것이라 예상하였다. 당연하게도 시간 초과로 실패하였다.

다시 접근

해당 문제는 DP문제였다. 이차원배열을 그리고 영역들을 색칠해가며 문제를 해석하니 문제를 풀 수 있는 방법이 보였다. 우선 배열에 값을 저장할 때 0에서부터 해당 지점까지의 수의 합을 저장한다. 이때 6X6배열에서 (3,4)까지의 합을 어찌구할지 고민이었는데 색칠을 하며 보니 쉽게 공식을 뽑아낼 수 있었다.

cin >> num;
matrix[i + 1][j + 1] = matrix[i][j + 1] + matrix[i + 1][j] - matrix[i][j] + num;

그 뒤에 M번 동안 해당 영역의 합을 구하는 공식도 영역에 색깔을 칠하는 방식으로 쉽게 공식을 추출할 수 있었다.

int result = matrix[x2][y2] - matrix[x1 - 1][y2] - matrix[x2][y1 - 1] + matrix[x1 - 1][y1 - 1];

하지만 아이러니하게도 또 시간 초과가 발생하였다. 구글링을 해도 이유를 알 수 없었다. 좀 시간이 지난 뒤에 cin의 속도 문제였음을 알게 되고 매우 허무하였다...