BaekJoon 2176번, 11660번: 부분합 구하기

#BOJ #baekjoon #알고리즘 #부분합 #2차원배열 #구간합 이번에는 BOJ 사이트에서 2차원 배열의 부분합을 구하는 문제에 DP(dynamic programming) 기법을 적용해서 문제를 풀어봤습니다. https://www.acmicpc.net/problem/11660 https://www.acmicpc.net/problem/2167 저는 두 문제가 유사하다고 판단하어 2167번 문제를 먼저 풀고난 후에 코드를 약간 수정해서 11660번 문제를 풀었습니다. 두 문제에서 2차원 배열 상에서 구간의 합을 구할 때, 배열의 해당 구간을 모두 방문하여 더해주도록 코딩하는 경우 시간초과로 인해 정답처리가 되지 않는 문제가 발생했습니다. 그에 따라서 DP 기법을 적용해 구간의 합을 O(n * n) or O(n * m)의 시간 복..........

원문링크 : BaekJoon 2176번, 11660번: 부분합 구하기