프로그래밍

https://programmers.co.kr/learn/courses/30/lessons/92344

[난이도] level3
[유형] 누적합

[풀이]
공식풀이 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

#include <string>
#include <vector>
using namespace std;
int sum[1002][1002],N,M;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    N=board.size();
    M=board[0].size();
    for(auto s : skill){
        int d=s[5];
        if(s[0]==1) d*=-1;
        sum[s[1]][s[2]]+=d;
        sum[s[3]+1][s[2]]+=-d;
        sum[s[1]][s[4]+1]+=-d;
        sum[s[3]+1][s[4]+1]+=d;
    }
    for(int i=0;i<N;i++)
        for(int j=1;j<M;j++) sum[i][j]+=sum[i][j-1];
 
    for(int i=0;i<M;i++)
        for(int j=1;j<N;j++) sum[j][i]+=sum[j-1][i];
 
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(board[i][j]+sum[i][j]>0) answer++;
 
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/파괴되지_않은_건물.cpp

https://www.acmicpc.net/problem/1749

[난이도] Gold4
[유형] 누적합

[풀이]
누적합을 미리 구해준 뒤 나올 수 있는 모든 부분행렬을 구해보면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[201][201],ans=-9e8;
int sol(int h,int w){
    int ret=-9e8;
    for(int i=1;i<=N-h+1;i++)
        for(int j=1;j<=M-w+1;j++)
            ret=max(ret,board[i+h-1][j+w-1] - board[i-1][j+w-1] - board[i+h-1][j-1] + board[i-1][j-1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%d",&board[i][j]);
            board[i][j]+=board[i][j-1]+board[i-1][j]-board[i-1][j-1];
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            ans=max(ans,sol(i,j));
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1749.cpp

https://programmers.co.kr/learn/courses/30/lessons/12984

[난이도] level4
[유형] 누적합

[풀이]
N*N의 최대가 300*300이기 때문에 모든 땅을 같은 높이로 맞춰보는 방법은 (300*300)^2 연산으로
O(N^4)의 시간복잡도를 필요로 하기 때문에 사용이 불가능합니다.

하지만 누적합 배열을 이용하면 쉽게 O(N^2) 으로 해결이 가능합니다.

1) 우선 2차원 land 배열을 1차원 배열 arr[90001]로 옮긴 뒤 정렬해줍니다.
   이제 N=N*N으로 바꿔줍니다.

2) sum[90001] 배열을 누적합을 저장합니다.

3) 최적의 높이는 arr[1] 또는 arr[2] ... arr[N] 입니다. 이 이외의 높이로 맞추는 것은
   비용을 더 늘어나게 합니다.
   그러므로 arr[i]의 각 높이로 맞춰보면서 비용이 최소가 될때를 찾으면 됩니다.

   예를 들어 N=6이고 각 땅의 높이가 [3,3,4,4,5,7] 일때 아래 그림을 참고해봅시다.
   (N은 k^2 꼴이여야 하지만 편의상 6으로 설정하였습니다.)

   높이를 arr[3]=4로 맞추고 싶을 때, 좌측의 4보다 높이가 작은 땅은 파란색 영역 만큼
   높이를 증가시켜야 하고, 우측의 높이가 4보다 높은 땅은 초록색 영역만큼 높이를 줄여야 합니다.
   이는 누적합 배열 sum을 이용해 아래와 같이 계산이 가능합니다.

   좌측 파란색 영역 =
   [높이가 arr[i]이고 넓이가 i-1인 직사각형 : arr[i]*(i-1)]  -  [1~(i-1)까지 땅 높이의 합 : sum[i-1]]
    = arr[i]*(i-1)-sum[i-1]

   우측 초록색 영역 =
   [i~N까지 땅 높이의 합 : sum[N]-sum[i-1]] - [높이가 arr[i]이고 넓이가 (N-(i-1))인 직사각형 : arr[i]*(N-(i-1))]
    = arr[i]*(i-1)-sum[i-1]

   좌측 값만큼 블록을 추가해야 하므로 P를 곱하고, 우측 값만큼 블록을 제거해야 하므로 Q를 곱한 뒤
   두 값을 더하면 최종 비용을 구할 수 있습니다.

   i:1~N 의 모든 값에 대해 위의 연산은 해주며 최소 비용을 구하면 최종 답을 구할 수 있습니다.
   (arr[i]가 동일한 땅들은 가장 앞에 있는 땅만 계산해주면 됩니다.)

파라메트릭 서치를 이용한 풀이도 있지만 위의 풀이가 좀 더 직관적이고 코드가 간결합니다.

#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
ll arr[90001],sum[90001],ans=-1;
int N;
ll solution(vector<vector<int> > land, int P, int Q) {
    N=land.size();
    int idx=1;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            arr[idx++]=land[i][j];
    N*=N;
    sort(arr,arr+N+1);
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+arr[i]; 
    int cur=-1;
    for(int i=1;i<=N;i++){
        if(arr[i]==cur) continue;
        cur=arr[i];
        ll v=0;
        v+=(sum[N]-sum[i-1]-arr[i]*(N-(i-1)))*Q;
        v+=(arr[i]*(i-1)-sum[i-1])*P;
        if(ans==-1 || ans > v) ans=v;
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/지형_편집.cpp

https://www.acmicpc.net/problem/11659

[난이도] Silver3
[유형] 누적합

[풀이]
구간합 배열 sum을 만들어놓고 sum[j]-sum[i] 형태로 모든 쿼리에 O(1)로 출력이 가능합니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N,M) = readLine().split(' ').map{it.toInt()}
    val arr = readLine().split(' ').map{it.toInt()}
    val sum = Array<Int>(N){0}
    sum[0]=arr[0]
    for(i in 1 until N) sum[i] = sum[i-1]+arr[i]
    while(M-->0){
        val ip = readLine().split(' ')
        val i = ip[0].toInt()
        val j = ip[1].toInt()
        println(sum[j-1]-(if(i==1) 0 else sum[i-2]))
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/11659.cpp

www.acmicpc.net/problem/10986

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고

만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

#include 
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<m;i++){ class="hljs-keyword" <span="">int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}</m;i++){>

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10986.cpp

www.acmicpc.net/problem/10986

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고
만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

#include <cstdio>
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<M;i++){
        int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10986.cpp