글 읽기 - 시간초과가 나온 이유가 뭘까요..?

pkc4913 5년 전 1

다음과 같이 풀었습니다

cur = 현재 음정

con = 연속해서 부른 음정의 갯수

con = 1이라면 dp[cur][con] = min(dp[cur - 1][k] + abs(A[cur] - A[cur - k - 1]) (k = 1 to cur - 1)

con != 1이라면 dp[cur][con] = dp[cur - 1][con - 1] + abs(A[cur] - A[cur - 1])

시간복잡도는 n^2이라고 생각해서 n = 2000정도는 가볍게 풀수 있을거라 생각했는데 어디서 잘못됐는지 모르겠습니다

혹시 반례가 있어서 무한루프를 도는걸까요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>
#include <queue>
#include <functional>
#include <time.h>
#include <set>

using namespace std;

int dp[2001][2001];
int A[2001];
int N;
const int inf = 99999999;

int solve(int cur, int con) {
	int &ret = dp[cur][con];
	if (ret != -1) return ret;
	if (cur == 1) {
		return ret = 0;
	}
	if (con != 1) {
		ret = 0;
		ret = solve(cur - 1, con - 1) + abs(A[cur] - A[cur - 1]);
	}
	else {
		ret = inf;
		for (int i = cur - 1; i >= 1; i--) {
			if(cur - i - 1 == 0) ret = min(ret, solve(cur - 1, i));
			else ret = min(ret, solve(cur - 1, i) + abs(A[cur] - A[cur - i - 1]));
		}
	}
	return ret;
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}
	int ret = inf;
	for (int i = 1; i <= N; i++) {
		memset(dp, -1, sizeof(dp));
		ret = min(ret, solve(N, i));
	}
	printf("%d", ret);
}

gs25 2년 전 0

혹시 시간초과 해결하셨나요? 거의 같은 알고리즘인데 시간초과 이유를 모르겠네요..

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

문제

문제

출처

ICPC

시간초과가 나온 이유가 뭘까요..?

pkc4913 5년 전 1

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말