[알고리즘][동적 계획법] 2차원 배열의 합 (백준)

2차원 배열의 합 - 동적 계획법 문제 (백준)

이 문제를 처음 보고 이게 왜 동적 계획법인가 의아했다.

그냥 아무 생각 없이 2중 for문을 돌려서 답을 찾았다.

너무 쉬운 문제라고 생각했다. 하지만 수행시간이 상당히 맘에 걸렸다.

다른 분들은 16MS가 나오는데 836MS가 떠버린 것..

수행 시간을 위해서라도 동적 계획법으로 풀어봐야겠다는 생각이들어서

나름 DP배열을 선언하고 활용하면서 문제를 다시 풀어보았다.

2차원 배열의 합(동적 계획법)

836MS에 비하면 반으로 줄었지만 16MS에 비하면 어마어마한 수치가 떠버렸다..

어떻게 풀었을지 힌트라도 얻고 싶은데.. 코드 오픈을 아무도 해놓지 않았다 ㅠ

01. 초기화

초기화를 할 때 DP배열 또한 초기화를 해주었는데

이전의 모든 값의 합을 저장하는 것이 아니라 한 행마다 따로따로 합을 계산했다.

02. 동적 계획법(다이나믹) 알고리즘

때문에 DP배열 x행의 y열을 선택하면 그 행의 y열까지의 최대 합이 들어있다.

그 합을 모두 더한 것에서 필요 없는 부분을 빼버리면 답을 구할 수 있다.

딱 보고 문제가 너무 쉬웠기 때문에 빨리 풀고 다음 문제로 넘어가야지 했는데

수행 시간 때문에 한참을 고전했던 것 같다. 완벽하게 수행 시간을 줄이지는 못했지만

계속해서 연구해봐야 할 가치가 있는 문제라고 생각한다.