백준 11660 : 구간합 구하기 5

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

---

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

 

구간 합을 2차원 배열로 구하는것

---

생각

1.  구간 합 문제
2.  일단 원하는데 까지 모두 더하고 필요없는 부분 빼기
3. 중복해서 뺀 부분 더해주기

 

---

코드

// 예시에서 a,b - c,d 까지 구하는것
// 일단 1,1 - c,d 까지의 합을 구함
// 1,1 - a,d 까지 빼고
// 1,1 - c,b 까지 뺵고
// 중복으로 뺀 1,1을 더해주면 됨됨 

// 3,3 4,4 -> 1,1 - 2,4 / 1,1 - 4,2 / 1,1 - 2,2


#include <iostream>
#include <vector>

using namespace std;
int main()
{
    // 입력값 받기
    int n, m;
    cin >> n >> m;
    // 일단 전체 구간 합

    vector<vector<int>> sums(n + 1, vector<int>(n + 1, 0));

    for(int ix = 1; ix <= n; ix++)
    {
        for(int jx = 1; jx <= n; jx++)
        {
            // 중복된 값을 빼줘야함
            cin >> sums[ix][jx];
            sums[ix][jx] += (sums[ix-1][jx] + sums[ix][jx-1] - sums[ix - 1][jx - 1]);
            //cout << sums[ix][jx] << " ";
        }
        //cout << "\n";
    }

    for(int ix = 0; ix < m; ++ix)
    {
        int x1, x2, y1, y2;
        cin >> x1, x2, y1 , y2;

        int a, b, c, d;
        a = x1 > y1 ? x1 : y1; 
        b = x2 > y2 ? x2 : y2; 
        c = x1 < y1 ? x1 : y1; 
        d = x2 < y2 ? x2 : y2; 

        cout << sums[a][b] - sums[c-1][b] - sums[a][d-1] + sums[c-1][d-1] << "\n";
    }
}

---

틀린 이유

• 범위 입력부분을 " , " 로 해서 문제가 발생
• 이 구간합 문제는 첫 입력이 두번째 입력을 넘지 않음

    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

• 입출력 동기화 해제 안함
• (x1, y1) , (x2, y2) 이렇게 해야하는데 (x1, x2) (y1, y2) 로 생각해 버려서 머리가 아파짐 -> 전제가 틀렸음

---

수정 코드

방법1

• 기존의 입력값이 이상하게 들어온다고 한 것을 생각 안하기로함

for(int ix = 0; ix < m; ++ix)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;

        int a, b, c, d;
        a = x1 > y1 ? x1 : y1; 
        b = x2 > y2 ? x2 : y2; 
        c = x1 < y1 ? x1 : y1; 
        d = x2 < y2 ? x2 : y2; 

        cout << sums[a][b] - sums[c-1][b] - sums[a][d-1] + sums[c-1][d-1] << "\n";
    }

 

for(int ix = 0; ix < m; ++ix)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << sums[x2][y2] - sums[x1-1][y2] - sums[x2][y2-1] + sums[x1-1][y1-1] << "\n";
    }

 

방법2

• 한줄씩 개산하는 방식으로 변경 -> 2차원을 1차원 여러개로 생각해서 풀기

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    
    // 입력값 받기
    int n, m;
    cin >> n >> m;
    // 일단 전체 구간 합

    vector<vector<int>> sums(n + 1, vector<int>(n + 1, 0));

    for(int ix = 1; ix <= n; ix++)
    {
        for(int jx = 1; jx <= n; jx++)
        {
            // 중복된 값을 빼줘야함
            cin >> sums[ix][jx];
            sums[ix][jx] += sums[ix][jx-1];
        }
    }

    for(int ix = 0; ix < m; ++ix)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int result = 0;
        for(int jx = x1; jx <= x2; jx++)
        {
            result += sums[jx][y2] - sums[jx][y1-1];
        }
        cout << result << "\n";
    }
}

 

 

---

결과

• 문제 풀이 시간 : 60분
• 메모리 :  6264 KB
• 시간 :  112 ms

  ---

배운점 및 고칠점

• 머리속으로 정리가 안되면 손으로 써야함
• 복잡한 문제면 최대한 쪼개는 방식을 생각해 보자
• 이상한 입력값에 대해 고민하지 말자? -> 이건 해야할거 같은데