글 읽기 - 시간초과

thkighie1224 2년 전 0

Memorization 으로 풀었는데요 ㅜ.ㅜ

시간 초과가 뜨네요...

가로 7 세로 3 인 경우

Cache[7][3] = (Cache[6][3]+Cache[1][3]) , (Cache[5][3]+Cache[2][3]) , (Cache[4][3]+Cache[3][3]) , (Cache[7][1]+Cache[7][2]) 중에서 작은 걸 고르는 식으로 계산 했습니다.

위와 같이 모든 경우를 다 계산 할 필요가 없는 문제인가요? 아니면 Memorization으로 풀면 안되는 문제인건가요 ㅜ.ㅜ?

											#include<iostream>
using namespace std;

int Cache[10001][101];
int Min(int a, int b)
{
	if (a > b)
		return b;
	return a;
}
int Square(int i, int k)
{
	int h1, temp, min = 987654321;
	if (Cache[i][k] > 0)
		return Cache[i][k];
	if (i == k)
		return Cache[i][k] = 1;
	if (i > k)
	{
		if (i%k == 0)
			return Cache[i][k] = i / k;
	}
	else
	{
		if (k%i == 0)
			return Cache[i][k] = k / i;
	}
	for (int t = 1; t <= i / 2; t++)
	{
		temp = Square(i - t, k) + Square(t, k);
		if (temp < min)
			min = temp;
	}
	for (int t = 1; t <= k / 2; t++)
	{
		temp = Square(i, k - t) + Square(i, t);
		if (temp < min)
			min = temp;
	}
	return Cache[i][k] = min;
}
int main(void)
{
	int N, M, h1,temp;
	cin >> N >> M;
	// N 세로 줄 M 가로 줄
	Cache[0][0] = 0;
	for (int i = 0; i <= N; i++)
		Cache[i][1] = i;
	for (int i = 0; i <= M; i++)
		Cache[1][i] = i;

	cout << Square(N, M);
	return 0;
}
										

baekjoon 2년 전 0

시간복잡도가 N^2M이 나오기 때문에 시간 초과를 받게 됩니다.

채워야 하는 테이블의 개수는 N*M개 인데, 28번 줄에서 for를 i/2까지 돌아버리기 때문에 각각의 칸을 채우는 시간복잡도가 O(N)이 되어버립니다.

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

문제

문제

출처

ACM-ICPC

시간초과

thkighie1224 2년 전 0

baekjoon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태