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

아이디어

ㅠㅠㅠㅠ..

처음엔 완전탐색으로 풀었었고(시간초과), 두번쨰는 bfs로 각각 dp를 만들어서 풀었고(시간초과)

마지막으로 입력과 동시에 dp를 만들어버리면서 풀었다.아래 3개 코드 모두 올리겠습니다.1. 완전탐색2. bfs + dp3. dp

바쁘신분은 3번 풀이만 보면 되겠습니다.

dp의 아이디어만 소개하겠습니다.

좌: 처음 dp만들기, 우 : (x1,y1) ~ (x2,y2) 구간합 구하기

처음 dp는 빨간 동그라미까지의 합을 구하기 위해서는 세모(주황색), 네모(초록색)는 더하고 X(파란색)는 두번 더해졌기 때문에 빼준다.

구간합을 구할떄는 x2,y2까지의 합(주황색)에서 초록색과 파란색 영역을 빼주면 보라색 구간은 두번 빼졌기 때문에 다시 더해준다.

1. C++ 풀이 ( 완전탐색 )

#include <bits/stdc++.h>

using namespace std;
struct x_y{
    int x1;
    int y1;
    int x2;
    int y2;
};
vector<x_y> v;
int board[1025][1025];
int N,M;

void section_sum(void){

    int x1,y1,x2,y2;
    int sum;
    x_y tmp;

    for(int i = 0 ; i< M; i++)
    {
        sum = 0;
        tmp=v[i];
        x1 = tmp.x1; y1 = tmp.y1;
        x2 = tmp.x2; y2 = tmp.y2;
        for(int row = x1 ; row<=x2 ; row++)
        {
            for(int col = y1; col<=y2 ; col++)
            {
                sum += board[row][col];
            }
        }
        cout << sum << endl;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i =1 ; i<= N; i++)
    {
        for(int j = 1 ; j<= N ; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp;
        }
    }

    for(int i = 0 ; i< M; i++)
    {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x_y tmp = {x1,y1,x2,y2};
        v.push_back(tmp);
    }
    section_sum();

}

2. C++ 풀이 ( BFS+DP )

#include <bits/stdc++.h>

using namespace std;
struct x_y{
    int x1;
    int y1;
    int x2;
    int y2;
};
vector<x_y> v;
queue<pair<int,int>> q;
int board[1025][1025];
int dp[1025][1025];
bool visited[1025][1025];
int N,M;

void bfs(int x1, int y1, int x2, int y2){
    q.push({x1,y1});
    dp[x1][y1] = board[x1][y1];
    visited[x1][y1] = true;
    while(!q.empty()){
        int row =q.front().first;
        int col = q.front().second;
        q.pop();
        dp[row][col] = board[row][col]+dp[row-1][col] + dp[row][col-1] - dp[row-1][col-1];
        if(row <x2 && col < y2)
        {
            if(visited[row+1][col] == false) {
                q.push({row+1,col});
                visited[row+1][col] =true;
            }
            if(visited[row][col+1] == false){
                q.push({row,col+1});
                visited[row][col+1]= true;
            } 
        }
        else if( row == x2 && col <y2){
            if(visited[row][col+1] == false){
                q.push({row,col+1});
                visited[row][col+1] = true;
            } 
        }
        else if(row <x2 && col == y2){
            if(visited[row+1][col] == false){
                q.push({row+1,col});
                visited[row][col+1] = true;
            } 
        }
    }
    cout << dp[x2][y2] << endl;
}
void section_sum(void){
    int x1,y1,x2,y2;
    int sum;
    x_y tmp;
    for(int i = 0 ; i< M; i++)
    {
        sum = 0;
        memset(dp,0,sizeof(dp));
        memset(visited,0,sizeof(visited));
        tmp=v[i];
        x1 = tmp.x1; y1 = tmp.y1;
        x2 = tmp.x2; y2 = tmp.y2;
        bfs(x1,y1,x2,y2);
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i =1 ; i<= N; i++)
    {
        for(int j = 1 ; j<= N ; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp;
        }
    }

    for(int i = 0 ; i< M; i++)
    {
        int x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x_y tmp = {x1,y1,x2,y2};
        v.push_back(tmp);
    }
    section_sum();
}

3. C++ 풀이 ( DP)

#include <bits/stdc++.h>

using namespace std;
int board[1025][1025];
int N,M;


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int x1,x2,y1,y2;
    for(int i =1 ; i<= N; i++)
    {
        for(int j = 1 ; j<= N ; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp+board[i-1][j] + board[i][j-1] - board[i-1][j-1];
        }
    }
    for(int i = 0 ; i< M; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << board[x2][y2] - board[x2][y1-1] - board[x1-1][y2] + board[x1-1][y1-1] << '\n';
    }
}