글 읽기 - 이 코드가 최악의 경우에 시간초과가 나야 정상이죠?

curnurx 7년 전 0

고수분들 worst case 검사좀 해주세여~

for 문이 좀 복잡한지라 혹시나 예외상황이 있을까해서요..

for문이 3중이라 시간초과가 나야 정상이라 생각하지만 0ms가 나와서

#include <stdio.h>

int main()
{
	int T, K, coin[101][2]; scanf("%d %d", &T, &K);
	
	for (int i = 0; i < K; i++)
		scanf("%d %d", &coin[i][0], &coin[i][1]);

	int dp[10001] = { 1, 0, };
	for (int i = 0; i < K; i++){
		int num = coin[i][1];
		for (int j = T - coin[i][0]; j >= 0; j--){
			if (!dp[j]) continue;

			for (int k = 1, add = coin[i][0]; k <= num; k++, add += coin[i][0]){
				int next = j + add;
				if (next > T) break;
				dp[next] += dp[j];
			}
		}
	}

	printf("%d\n", dp[T]);
	return 0;
}

ntopia 7년 전 11

시간복잡도 계산을 대충 해봤습니다 [...

아주 대충 연산량을 계산해보면 첫번째 줄의 식과 같겠죠. (coin[i] = i번째 동전의 가격, cnt[i] = i번째 동전의 개수)

이것의 상한은 n = 100, T = 10000, cnt[i] = 1000 인 경우겠죠. 그래서 2번째 식이 나옵니다.

그리고 coin[i] = i 인 경우가 worst case 겠죠. coin[i] 가 이것보다 크다면 연산량이 무조건 줄어듭니다. 그래서 4번째 식이 나옵니다.

이걸 풀어헤쳐보면 대략 3억 정도가 나오고, 전부 심플한 연산이라 일단 1초안에 safe하게 됩니다.

그리고 여기서 한가지 더.

실제로 위와 같은 최악의 case 를 만들어서 직접 넣어보면 2^31 을 아득히 뛰어넘는 경우의 수가 나오게 됩니다.

"방법 의 수는 2^31을 초과하지 않는 것으로 가정한다." 라는 조건 때문에 실제로 연산량은 훨씬 줄어들게 되어

0ms에 나오게 됩니다.

curnurx 7년 전 0

우와 친절한 답변 감사합니다! 좋은 하루~

kyr778 6달 전 0

헐 이 부분 고민이었는데 감사합니다!

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

문제

문제

출처

ICPC

이 코드가 최악의 경우에 시간초과가 나야 정상이죠?

curnurx 7년 전 0

ntopia 7년 전 11

curnurx 7년 전 0

kyr778 6달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말