[BOJ알고리즘, C++]#11660_구간 합 구하기 5

2022. 8. 14. 21:35· 문제 풀이/BOJ 문제 풀이
목차
  1. [BOJ 알고리즘, C++] #11660_구간 합 구하기 5

[BOJ 알고리즘, C++] #11660_구간 합 구하기 5

 

BOJ 알고리즘 문제 풀이, 11660_구간 합 구하기 5

누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제

 

 


 

문제

 

풀이

 

1. 먼저, 2차원 배열의 누적합을 "열" 순으로 누적 합을 계산하는 것이 아니라, "행" 순으로 계산해야 합니다.

2. 누적 합을 계산하는 방법은 아래와 같이 "[i-1][j] + [i][j-1] - [i-1][j-1]"입니다.

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]

 

 

"행"을 기준으로 누적 합을 계산하다 보면 "중복"으로 누적된 값이 존재합니다! 

 

위 그림을 살펴보면, prefixSum[4]를 위해 prefixSum[2]와 prefixSum[3]의 값이  필요하지만,

이 둘은 이전 누적 합 계산에서 공통적으로 prefixSum[1]이 누적이 되었죠!

 

따라서, 정확한 누적 합 계산을 위해 중복되는 누적 합 부분을 빼주는 것이 필요합니다!

 

코드
#include <iostream>
using namespace std;

int arr[1025][1025];
int dp[1025][1025];
int N, M;
int ans;

int main()
{
    // 수행 시간 감소를 위한 라인
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
    cin >> N >> M;
    
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j];
        }
    }
    
    for(int i=0; i<M; i++)
    {
        int firstX, firstY, secondX, secondY;
        cin >> firstX >> firstY >> secondX >> secondY;
        
        ans = dp[secondX][secondY] - dp[firstX-1][secondY] 
            - dp[secondX][firstY-1] + dp[firstX-1][firstY-1];
        
        cout << ans << '\n';
    }
}


// 참조 : https://donggoolosori.github.io/2020/10/13/boj-11660/ 

/************************** 시간 초과 실패 코드 **************************/

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

// typedef long long ll;

// int N, M;

// vector<ll> prefixSum(1,0);

// long long calcInterval(const int firstA, const int firstB, const int secondA, const int secondB)
// {
//     ll ans;
//     ll left =0, right =0; 
    
//     for(int i=0; i<=(secondA - firstA); i++)
//     {
//         left = (N*firstA) - (N-firstB) + (N*i);
//         right = (N*firstA) - (N-secondB) + (N*i);
        
//         ans += prefixSum[right] - prefixSum[left-1];
//     }
    
//     return ans;
// }

// int main()
// {
//     // 수행 시간 감소
//     ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
//     cin >> N >> M;
    
//     for(int i=1; i<=(N*N); i++)
//     {
//         ll tmp;
        
//         cin >> tmp;
//         prefixSum.push_back(prefixSum[i-1] + tmp);
//     }
    
//     for(int i=0; i<M; i++)
//     {
//         // [A1][B1], [A2][B2]
//         int a1, b1, a2, b2;
//         int ret;
        
//         cin >> a1 >> b1 >> a2 >> b2;
        
//         ret = calcInterval(a1, b1, a2, b2);
        
//         cout << ret << '\n';
//     }
// }

 

 

 

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#11050_이항 계수 1, 이항 계수 공식, 재귀문 활용  (0) 2022.09.04
[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법  (0) 2022.09.04
[BOJ알고리즘, C++]#2559_수열의 최대 구간 합, 누적 합 알고리즘  (0) 2022.07.12
[BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘  (0) 2022.06.29
[BOJ알고리즘, C++]#15649 N과 M(1), 깊이 정렬, DFS  (0) 2022.02.12
  1. [BOJ 알고리즘, C++] #11660_구간 합 구하기 5
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#11050_이항 계수 1, 이항 계수 공식, 재귀문 활용
  • [BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법
  • [BOJ알고리즘, C++]#2559_수열의 최대 구간 합, 누적 합 알고리즘
  • [BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 개발
  • DP
  • 알고리즘
  • C++
  • BOJ
  • 최단 경로
  • 트리
  • set
  • 그래프
  • 정렬
  • dfs
  • BFS
  • 기술 질문
  • Effective C++
  • stl
  • unreal
  • Unreal Blueprint
  • 디자인 패턴
  • programmers
  • 우선순위 큐

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#11660_구간 합 구하기 5
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.