글 읽기 - 띠용 이거는 왜 시간초과가 날까요?...

s7d8f9 3년 전 0

밑에 코드에서 전역변수를 다음과 같이 하면 통과가 되고

int dp[1500005];
int n;

다음과 같이 한줄에 쓰면 시간초과가 발생하는데 원인이 뭘까요?..

int n, dp[1500005];

#include <iostream>
using namespace std;
int dp[1500005];
int n;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int day, money;
		scanf("%d%d", &day, &money);
		dp[i + 1] = dp[i + 1] < dp[i] ? dp[i] : dp[i + 1];
		dp[i + day] = dp[i + day] < dp[i] + money ? dp[i] + money : dp[i + day];
	}
	printf("%d", dp[n + 1]);
	return 0;
}

djm03178 3년 전 1

day가 커서 12번째 줄에서 배열의 범위를 벗어나기 때문에 어떤 동작을 하게 될지 알 수 없습니다. 전자는 '운이 좋아서' 통과될 뿐입니다.

s7d8f9 3년 전 0

앗 감사합니다. .ㅎ

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

문제

문제

출처

ICPC

띠용 이거는 왜 시간초과가 날까요?...

s7d8f9 3년 전 0

djm03178 3년 전 1

s7d8f9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말