글 읽기 - 시간초과 해결책 부탁드립니다.

kbmin24 3년 전 0

다른 질문에서 어떤 분이 말씀해 주신 대로 다음과 같은 방법으로 코드를 구현했습니다 (https://www.acmicpc.net/board/...).

각 열을 1차원 배열로 보고 prefix sum 전처리를 합니다.
직사각형의 위와 아래 경계를 이루는 행을 i와 j로 고정했다고 하면, 이제 열의 구간을 선택하는 문제만 남습니다.
- 따라서, 앞서 전처리한 결과를 이용해 각 열 k에 대해 입력배열의 부분합 A[k][i] + ... + A[k][j]를 구해줍니다. 이를 B[k]라고 합시다.
- B[k]에 대한 문제는 언급하신 10986번 문제와 정확히 같은 방법으로 O(M)에 해결할 수 있습니다.

제가 구현한 코드에서 42줄부터 53줄까지가 10986번 문제와 같이 각 부분합에 대하여 가짓수를 찾는 부분인데, 문제는 이 과정에서 k번(최대 100만회) 루프하다 보니 시간 초과가 납니다.

혹시 이 부분을 다르게 구현할 수 있는 방법이 있을까요?

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <time.h>

#define endl "\n"
using namespace std;

static int number[257][257];
static int bubun[257][257];
static int rem[1000001];
int rBubun[257];
stack<int> mods;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	clock_t start, end;

	long long ans = 0;
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			int tmp;
			cin >> tmp;
			bubun[i][j] = bubun[i - 1][j] + tmp;
		}
	}
	start = clock();
	for (int i = 1;i <= n;i++)
	{
		for (int j = i;j <= n;j++)
		{
			//cout << i << " " << j << " ..." << endl;
			for (int l = 1;l <= m;l++)
			{
				rBubun[l] = (rBubun[l - 1] + (bubun[j][l] - bubun[i - 1][l])) % k;
				rem[rBubun[l]]++;
			}
			int localAns = rem[0];
			for (int l = 0;l < k;l++)
			{
				localAns += (rem[l] * (rem[l] - 1)) / 2; //rem[l]C2
				rem[l] = 0;
			}
			ans += localAns;
		}
	}
	end = clock();
	cout << ans << endl;
	cout << (double)(end - start) << "ms" << endl;
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 해결책 부탁드립니다.

kbmin24 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말