BOJ_구간 합 구하기 5_11660 (Java, C++)

융바오·2024년 12월 18일

C++Java 백준 알고리즘

Problem Solving

목록 보기

9/89

문제 링크

성능 요약

Java - 메모리: 129240 KB, 시간: 948 ms
C++ - 메모리: 10412 KB, 시간: 152 ms

분류

다이나믹 프로그래밍, 누적 합

제출 일자

2024년 12월 18일 17:27:36

문제 설명

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이다.

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

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

느낀점

누적합에서 구간합을 구할때 범위에 따른 계산법이 다르다!

설계 : 10분

누적합 배열을 생성한 다음, 누적합 배열을 통해 구간합을 구한다.

코드(Java)

구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 구간 합 구하기 5_11660
 * Date: 2024.12.18
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int arr[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int prefixSum[][] = new int[n][n];
        prefixSum[0][0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            prefixSum[0][i] = prefixSum[0][i - 1] + arr[0][i];
            prefixSum[i][0] = prefixSum[i - 1][0] + arr[i][0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + arr[i][j];
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int stX = Integer.parseInt(st.nextToken()) - 1;
            int stY = Integer.parseInt(st.nextToken()) - 1;
            int endX = Integer.parseInt(st.nextToken()) - 1;
            int endY = Integer.parseInt(st.nextToken()) - 1;

            int answer = prefixSum[endX][endY];
            if (stX > 0) answer -= prefixSum[stX - 1][endY];
            if (stY > 0) answer -= prefixSum[endX][stY - 1];
            if (stX > 0 && stY > 0) answer += prefixSum[stX - 1][stY - 1];

            bw.write(String.valueOf(answer) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

코드(C++)

구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 구간 합 구하기 5_11660
 * Date: 2024.12.18
 */

#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    cin.ignore();

    vector<vector<int>> arr(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        string input;
        getline(cin, input);
        stringstream ss(input);
        for (int j = 0; j < n; j++) {
            ss >> arr[i][j];
        }
    }

    vector<vector<int>> prefixSum(n, vector<int>(n));
    prefixSum[0][0] = arr[0][0];
    for (int i = 1; i < n; i++) {
        prefixSum[i][0] = prefixSum[i-1][0] + arr[i][0];
        prefixSum[0][i] = prefixSum[0][i-1] + arr[0][i];
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + arr[i][j];
        }
    }

    for (int i = 0; i < m; i++) {

        string input;
        getline(cin, input);
        stringstream ss(input);
        int stX, stY, endX, endY;
        ss >> stX >> stY >> endX >> endY;

        int answer = prefixSum[endX-1][endY-1];
        if (stX > 1) answer -= prefixSum[stX-2][endY-1];
        if (stY > 1) answer -= prefixSum[endX-1][stY-2];
        if (stX > 1 && stY > 1) answer += prefixSum[stX-2][stY-2];

        cout << answer << "\n";
    }

    return 0;
}

알게된 점
- 입출력이 많은 문제여서 cin, cout 을 사용하니 시간초과가 났다.
- c++에서 빠른입출력을 하기 위해서는 두가지 방법이 있다.
  - 한줄 읽기: getline()과 stringstream 사용 (버퍼를 사용함)
```
string input;
getline(cin, input);
stringstream ss(input);
for (int j = 0; j < n; j++) {
    ss >> arr[i][j];
}
```
  - C언어 스타일의 scanf, printf (포맷 지정자를 사용, C++스타일과의 혼용 주의)
```
int n, m;
scanf("%d %d", &n, &m);

vector<vector<int>> arr(n, vector<int>(n));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        scanf("%d", &arr[i][j]);
    }
}
```
- 추가 설정
  - ios_base::sync_with_stdio(false):
    - C++ 표준 스트림(cin, cout)과 C 표준 스트림(scanf, printf) 간의 동기화를 비활성화
    - 이로 인해 C++ 표준 스트림이 더 빠르게 작동
  - cin.tie(nullptr):
    - cin과 cout의 묶임(tie)을 끊음
    - 기본적으로 cin을 호출하면 자동으로 cout이 flush(버퍼 비우기)되는데, 이를 방지하여 속도 향상
- vector<vector<int>> arr(n, vector<int>(n)); 여기서 >>를 연산자로 인식하여 오류가 발생하는 경우는 컴파일러의 C++ 버전을 확인(11 이상)해봐야한다.
  - 버전설정으로 문제를 해결하기 어렵다면 우회방법으로 > > 처럼 사이에 공백을 넣는다.