글 읽기 - 시간복잡도가 얼마나 나와야 할까요?

ikasty 6년 전 0

다이나믹 프로그래밍을 이용해 O(n^2)로 코드를 작성했는데요, (사실 맞는지도 확실치는 않지만) 채점을 하면 계속해서 시간 초과라고 뜨네요.

작성한 코드의 방향이 맞는지조차 확신이 들지 않아서 질문을 드립니다.

부족하지만 제가 작성한 탐색하는 부분 코드를 대략적으로 올려봅니다.

고수님들의 답변을 기다립니다.

for (int i = 1; i < n; i++) {
	for (int j = i + 1; j <= n; j++) {
		if (line_exist(i, j)) continue;
		if (sum[i] + value[j] > sum[j]) {
			sum[j] = sum[i] + value[j];
			track[j] = i;
		}
		if (max < sum[j]) {
			max = sum[j];
			find = j;
		}
	}
}

irishw 6년 전 0

n 10000인데,

n^2 이면 1억,

O(1억)이면 대략 1초...

전체 코드를 봐야 하겠지만, 일단 부분 시간복잡도는 1만^2으로 풀면 안되것 같습니다.

그리고 답을 찾았을 경우, max 갱신 할때마다, find=j구문으로,

최종 독립집합의 값들을 출력하기 어려워 보입니다.(이것도 전체코드를 몰라서;;;)

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

문제

문제

출처

ICPC

시간복잡도가 얼마나 나와야 할까요?

ikasty 6년 전 0

irishw 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말