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

kiwonlee95 4년 전 0

2차원 배열의 부분합을 구하고

전체 경우의 수를 for문으로 돌면서 계산하는 방법인데

시간초과가 발생합니다.

이 코드에서 시간초과 문제를 해결할 수 있는 방법을 부탁드립니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#pragma warning(disable : 4996)
using namespace std;

const int MAX_NUM = 300;

int num[MAX_NUM + 1][MAX_NUM + 1];
int N, M, K;
int ans;

vector<vector<int>> getPartialSum()
{
	vector<vector<int>> sum(N, vector<int>(M));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (i == 0 && j == 0)
				sum[i][j] = num[i][j];
			else if (i == 0 && j != 0)
				sum[i][j] = sum[i][j - 1] + num[i][j];
			else if (i != 0 && j == 0)
				sum[i][j] = sum[i - 1][j] + num[i][j];
			else
				sum[i][j] = num[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

	return sum;
}

int getSum(const vector<vector<int>> & psum, int x1, int y1, int x2, int y2)
{
	int ret = psum[x2][y2];

	if (x1 > 0) ret -= psum[x1 - 1][y2];
	if (y1 > 0) ret -= psum[x2][y1 - 1];
	if (x1 > 0 && y1 > 0) ret += psum[x1 - 1][y1 - 1];

	return ret;
}

int main()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &num[i][j]);

			if (num[i][j] % K == 0)
				ans++;
		}
	}

	vector<vector<int>> psum = getPartialSum();

	
	for (int x_start = 0; x_start < N; x_start++)
	{
		for (int x_size = 1; x_size + x_start < N; x_size++)
		{
			for (int y_start = 0; y_start < M; y_start++)
			{
				for (int y_size = 1; y_size + y_start < M; y_size++)
				{
					int sum = getSum(psum, x_start, y_start, x_start + x_size, y_start + y_size);

					if (sum % K == 0)
						ans++;
				}
			}
		}	
	}

	printf("%d\n", ans);

    return 0;
}

kiwonlee95 4년 전 0

답변 감사합니다.

답변에서 올려주신 10986번 풀어서 부분합의 나머지를 계산하는 알고리즘을 배웠습니다.

그런데 행렬에 적용하려니 잘 떠오르지가 않는데

답변에서 이어지는 부분과 사이사이에 있는 부분이 어떤 걸 말하는지 부탁드립니다.

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

문제

문제

출처

ICPC

2369 시간 초과 문제 해결 부탁드립니다.

kiwonlee95 4년 전 0

kiwonlee95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말