Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • KMP
  • 세그먼트 트리
  • 트라이
  • C++
  • 정렬
  • 정수론
  • 큐
  • 동적계획법
  • 문자열
  • 트리
  • 이분탐색
  • 조합론
  • 분할정복
  • 백준
  • 최소 스패닝 트리
  • 수학
  • 구현
  • 유니온 파인드
  • 위상 정렬
  • 우선순위큐
  • 스택
  • 그래프
  • 백트래킹
  • 투포인터
  • UC++
  • 기하
  • SCC
  • 브루트포스
  • LCA
  • 누적합

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++] 백준 - 2167번 문제
공부 및 정리/백준 코드

[C++] 백준 - 2167번 문제

2022. 12. 13. 17:38

2167번: 2차원 배열의 합 (acmicpc.net)

 

2167번: 2차원 배열의 합

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는

www.acmicpc.net

 

2167번 : 2차원 배열의 합


2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

 

입력


첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M).

 

 

출력


K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다.

 

 

 


 

생각해 볼 점


누적합 문제입니다.

 

가로, 세로 누적합을 해두고 구간 합을 구할 수 있습니다.

 

예시)

초기 배열

0 0 0 0
0 1 2 4
0 8 16 32

 

가로 누적합

0 0 0 0
0 1 3 7
0 8 24 56

 

세로 누적합

0 0 0 0
0 1 3 7
0 9 27 63

 

 

- (i, j) ~ (x, y)의 구간 합을 구하는 방법

 

위의 누적합 배열에서 

 

arr[x][y] - arr[i-1][y] - arr[x][j-1] + arr[i-1][j-1] 이 구간 합입니다.

 

 

아래는 원리입니다.

 

1. 파란 영역은 arr[x][y]가 나타내는 누적합 영역으로

(1,1)에서 (x,y)까지 모두 합한 합을 의미합니다.

 

2. 빨간 영역은 arr[x][j -1]이 나타내는 영역으로

(1, 1)에서 (x, j - 1)까지의 합을 나타냅니다.

 

3. 위의 자두색 영역은 arr[i - 1][y]가 나타내는 영역으로

(1,1)에서 (i - 1, y)까지의 합을 나타냅니다.

 

파란 영역에서 빨간 영역, 자두색 영역을 빼면..

 

좌측위의 겹치는 부분이 두번 빼지게 됩니다.

 

4. 따라서, arr[i - 1][j - 1]을 한번 더해주어 수식을 완성합니다.

 

결과적으로 A - B - C + D가 됩니다.

 

 

코드


#include <iostream>
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);

    int arr[301][301] = {0, };
    
    //가로 누적합
    for(int y = 1; y <= N; y++)
    {
        for(int x= 1; x <= M; x++)
        {
            scanf("%d", &arr[y][x]);
            arr[y][x] += arr[y][x - 1];
        }
    }

    //세로 누적합
    for(int x = 1; x <= M; x++)
    {
         for(int y= 1; y <= N; y++)
            arr[y][x] += arr[y-1][x];
    }

    int K;
    scanf("%d", &K);

    int i, j, x, y;
    for(int k = 0; k < K; k++)
    {
        scanf("%d %d %d %d", &i, &j, &x, &y);
        printf("%d\n", arr[x][y] - arr[x][j - 1] - arr[i - 1][y] + arr[i - 1][j - 1]);
    }
    return 0;
}

 

그 외


 

저작자표시

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++] 백준 - 11056번 문제  (1) 2022.12.21
[C++] 백준 - 2240번 문제  (0) 2022.12.19
[C++] 백준 - 2096번 문제  (0) 2022.12.01
[C++] 백준 - 2342번 문제  (0) 2022.11.30
[C++] 백준 - 1202번 문제  (0) 2022.11.18
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++] 백준 - 11056번 문제
    • [C++] 백준 - 2240번 문제
    • [C++] 백준 - 2096번 문제
    • [C++] 백준 - 2342번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바