알고리즘/Prefix Sum1 [prefix sum] 백준 11660번 - 구간 합 구하기 5 pre 배열을 (1,1)에서 (i,j)까지 정사각형 모양의 값들의 합이라고 한다면 (a, b) ~ (c, d)의 값을 구한다고 한다면 답 : pre[c][d] - pre[c][a-1] - pre[a-1][d] + pre[a-1][b-1] 그렇다면 pre 값들은 어떻게 구할 수 있을까 마찬가지로 i j 이중 for문을 돌리면서 값을 받을 때 이전의 값을 참조하면 된다 pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + input 시간 복잡도 : O(max(N^2, M)) #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M.. 2021. 2. 16. 이전 1 다음
