22.07.10. 풀었던 문제들

BOJ 단계별 17 누적합

11659 구간 합 구하기 4

2559 수열 - partial sum으로 해도 되고, sliding window로 풀어도 된다. 근데 문제 특성상 k가 주어지기 때문에 sliding window로 푸는 게 더 쉬울 듯.

16139 인간-컴퓨터 상호작용 - 알파벳 별로 누적합을 만들어야 했음

10986 나머지 합 - 흥미로운 문제. psum을 구할 때 % 연산을 하고, 해당 값이 몇 번 나왔는지를 기록한다. 그리고 모든 %값의 개수에 대해, combination 2를 택해주고(% M이 같은 두 구간을 뺀다면 그 구간은 M의 배수이다. 이 구간 중 순서 상관없이 2개를 택하는 경우의 수), 마지막으로 0이 나온 횟수(첫번째부터 i까지 %K == 0이라는 의미)를 더해주면 된다.

int main(void) {
	cin.tie(0);
	cout.tie(0);
	std::ios_base::sync_with_stdio(0);
 
	////////////////////// write your code below
	
	ll N, M; cin>>N>>M;
	vector<ll> arr(N);
	for(ll i = 0; i<N; i++) cin>>arr[i];
 
	vector<ll> psum(N);
	vector<ll> cnt(M, 0);
	psum[0] = arr[0] % M;
	cnt[psum[0]]++;
	for(ll i = 1; i<N; i++){
		psum[i] = (psum[i-1] + arr[i]) % M;
		cnt[psum[i]]++;
	}
 
	ll answer = 0;
	for(ll i = 0; i<M; i++){
		answer += cnt[i] * (cnt[i] - 1) / 2;
	}
	cout<<answer + cnt[0];
 
	//////////////////////
 
	return 0;
}

11660 구간 합 구하기 5 - 2차원 psum 문제

 

Codeforces #787 Div. 3 Upsolving

E