[백준 11660] 구간 합 구하기 5 (C++)

https://www.acmicpc.net/problem/11660

 

 

DP 동적계획법

이런 표에서 주황색 점 위치(시작점)와 파란색 점 위치(끝점)가 주어지면, 빨간테두리의 박스에 속한 숫자들의 합을 구하는 문제

근데 이제 빨간 박스가 M개 주어지고 M이 100,000까지 될 수 있고, NxN에서 N은 1024까지 될 수 있는..

 

접근 방법

처음에 엥 표 저장해두고 [r1][c1] ~ [r2][c2] 까지 다 더하면 되는거 아닌가? 했지만 실버1인걸 보고 DP로 풀었음..

이전에 내가 생각해온 DP는 미리 구해놓고 쓰기 였는데 예를들면 한 행에서 각 원소의 값을 그 원소까지의 합으로 치환한다.

위의 표에서 첫번째 행을 예로들면, 1 2 3 4 -> 1 3(1+2) 6(1+2+3) 10(1+2+3+4).

이때 치환할 때는 본인 + 본인 이전 칸의 수를 다시 본인 칸에 대입해주면 된다. 

그러면 1칸부터 4칸까지의 합을 구할때는 4칸만 출력하면 되고, 2~4칸 까지의 합을 구할 때는 4칸 - (2-1)칸 을 출력하면 된다. 

4칸 = 1~4칸의 합이고, 1칸 = 1칸까지의 합이니까 빼면 2~4칸 까지의 합이 됨.

 

근데 이번에는 2차원 배열이라 가로로 더해둔다고 쳐도 필요한 행만큼 이 동작을 반복해줘야 하는데

그래서 살짝 시간초과가 날까 걱정했지만 다행히 통과 됨..ㅎ

 

오답노트

아니 이 문제 풀면서 로직 오류는 아닌 것 같은데

이상하게 xcode에서 m행, 4열 반복문을 도는데 무슨 귀신씌인거마냥 i가 자꾸 m까지 가서 범위를 벗어남..

근데 똑같은 코드를 지웠다가 다시쓰니까 됨;;;

이런 오류가 종종 있는건지..아시는 분..

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,m;
    cin >> n >> m;

    vector<vector<int>> board(n+1, vector<int>(n+1, 0));
    
    int num;
    for(int r = 1; r <= n; r++){
        for(int c = 1; c <= n; c++){
            cin >> num;
            board[r][c] = board[r][c-1] + num;
        }
    }
    
    vector<vector<int>> ranges(m, vector<int>(4));
    for(int i = 0 ; i < m ; i++){
        for(int j = 0 ; j < 4 ; j++){
            cin >> ranges[i][j];
        }
    }
    
    for(int i = 0 ; i < m ; i++){
        int r1 = ranges[i][0];
        int c1 = ranges[i][1];
        int r2 = ranges[i][2];
        int c2 = ranges[i][3];
        int result = 0;
        for(int r = r1; r <= r2; r++){
            result += (board[r][c2] - board[r][c1-1]);
        }
        cout << result << "\n";
    }
    
    
    return 0;
}