글 읽기 - [C++17] 질문글이 잘 이해가 가지 않습니다.

choah76 1년 전 0

https://www.acmicpc.net/board/...

위 질문글에 나온 대로 알고리즘을 짜고 있는데, 어떤 부분을 놓치고 있는지를 잘 모르겠습니다.

도움부탁드립니다.

예제에 나온 입력이 들어왔을 때 제 알고리즘이 동작하는 방식을 설명드리면,

1 2 3 2 1

remain[0] = [1,2,4]

remain[1] = [0, 3]

// 27~32줄

r = 0일때

ans += 3 : (1,2], (1,4], (2, 4] 3가지 경우

r = 1일때

ans += 1 : (0, 3] 1가지 경우

// 34줄

ans += 3 : [0, 1], [0, 2], [0, 4] 3가지 경우

출력: 7

정답: 7

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

#define MAXN 1000000
#define MAXM 1000
typedef long long ll;

ll pSum[MAXN];    // pSum[i] = 0번째 수부터 i번째 수까지의 누적합
// remain[i] = 0번부터 j번째까지의 누적합중 M으로 나눈 나머지가 i인 것의 인덱스 j가 저장된 벡터 (j<N)
vector<vector<int>> remain(MAXM);

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N, M, ans = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> pSum[i];
		if (i > 0)
			pSum[i] += pSum[i - 1];

		remain[pSum[i] % M].push_back(i);
	}

	for (int r = 0; r < M; r++) {
		if (!remain[r].empty()) {
			int n = remain[r].size();
			ans += n * (n - 1)/2;
		}
	}
    // 나머지가 0인 누적합구간 추가
	ans += remain[0].size();

	cout << ans;

	return 0;
}

zenith82114 1년 전 1

로직은 맞는 것 같은데 31줄 오버플로우만 처리해주시면 맞을지도 모르겠네요.

choah76 1년 전 0

정말 감사합니다

오버플로우문제가 맞았네요!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++17] 질문글이 잘 이해가 가지 않습니다.

choah76 1년 전 0

zenith82114 1년 전 1

choah76 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말