11659번⭐

수도 코드

N (숫자 개수), M (질의 개수), S (합 배열)

for(N만큼 반복):

	합 배열 생성 (S[i] = S[i-1] + A)

for(M만큼 반복):

	질의 범위 받기 (i ~ j)
    
    부분 합 출력 (S[j] - S[i-1])

답안

#include <iostream>

using namespace std;
int N; // 수의 개수
int M; // 질의 개수
int S[100004];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> M;
    S[0] = 0;
    int temp;
    for(int i = 1; i<=N; i++){
        cin >> temp;
        S[i] = S[i-1] + temp;
    }
    int startN, endN;
    for(int j = 0; j <M; j++){
        cin >> startN >> endN;
        cout << S[endN] - S[startN - 1] << "\n";
    }
}

11660번

아이디어

• 2차원 구간 합

수도 코드

N (배열 크기), M (질의 수), S (합 배열)

for(i-> 1이상 N이하):

	for(j-> 1이상 N이하):
    
    	합 배열 저장
        
        S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + temp
        
for(M만큼 반복):

	질의 계산 및 출력
    
    결과 = S[r2][c2] - S[r1-1][c2] -S[r2][c1-1] + S[r1-1][c1-1]

답안

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  cin >> N >> M;
  vector<vector<int>> S(N+1,vector<int>(N+1, 0));
  int temp;
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <=N; j++){
      cin >> temp;
      S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + temp;
    }
  }
  int x1,y1,x2,y2;
  for(int i = 0; i < M; i++){
    cin >> x1 >> y1 >> x2 >> y2;
    cout << S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1] << "\n";
  }
}

10986번

아이디어

• 구간 합 배열을 주어진 숫자로 나머지 연산을 하고 그 값이 두 개 이상 존재한다면 해당 부분 합에 대해 나누어 떨어진다.
  S[j] - S[i-1] == A[i] + ... + A[j]
(S[j] - S[i-1]) % C == (A[i] + ... + A[j]) % C
i 부터 j 까지의 숫자의 합이 C 로 나누어 진다면
  (S[j] - S[i-1]) % C == 0
(S[j] % C - S[i-1] % C) % C == 0
S[j] % C - S[i-1] % C 가 C 의 배수가 되고
  0 <= S[j] % C < C , 0 <= S[i-1] % C < C 이므로 C 보다 큰 배수는 될 수 없다.
  따라서 S[j] % C - S[i-1] % C == 0 이 된다.
  즉, S[j] % C == S[i-1] % C 이다

수도 코드

N (수열의 개수), M (나누어 떨어져야 하는 수)

S (합 배열:int), C (같은 나머지를 가지는 인덱스를 카운트하는 배열:long long)

for(i-> 1이상 ~ N이하):

	// 구간 합 배열 저장
    
    S[i] = S[i-1] + A[i] 
    
for(i-> 1이상 N이하):

	remainder = S[i] % M // 합 배열을 M으로 나눈 나머지 값
        
    C[remainder] += 1 // 나머지에 대한 개수 
    
for(i=-> 0이상 M미만): // S[0]을 0으로 세팅해서 S[i] == 0 인 경우도 카운트해야한다.
	
    if(C[i] > 1): // 2개 이상이면 부분 합이 0이 되는 구간이 있다
	
    	// C[i]개중에 2개 뽑아서 정답 개수에 더하기
    
    	answer += C[i] * (C[i] - 1) / 2 // 범위가 크므로 long long 타입
    
정답 출력

답안

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  cin >> N >> M;
  vector<int> S(N+1, 0);
  vector<long long> C(M, 0); 
  
  for(int i = 1; i <= N; i++){
    int temp;
    cin >> temp;
    S[i] = (S[i-1] + temp % M) % M;
  }
  
  long long answer = 0;
  for(int i = 0; i <= N; i++){
    C[S[i]]++;
  }
  for(int i = 0; i < M; i++){
    if(C[i] > 1){
      answer += C[i] * (C[i]-1) / 2;
    }
  }
  cout << answer << "\n";
}