글 읽기 - 시간 초과 인 이유를 알고 싶습니다.

fpdkf2580 3년 전 0

단일 for문인데도 시간 초과인 이유가 있을까요..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h> //난수 
#include <math.h>
#define max(a,b) (a) > (b) ? (a) : (b)


int dp[1001];
int T[1001];
int M[1001];
int main()
{
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d %d", &T[i], &M[i]);
	}
	for (int i = N; i >= 1; i--)
	{
		if (i + T[i] > N+1)
		{
			dp[i] = dp[i + 1];
		}
		else
		{
			dp[i] = max(dp[i + 1], M[i] + dp[T[i] + i]);
		}
	}
	printf("%d", dp[1]);


}
	
	

djm03178 3년 전 0

N의 범위는 최대 150만입니다. 그런데 배열의 크기는 다 1001이네요.

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

문제

문제

출처

ICPC

시간 초과 인 이유를 알고 싶습니다.

fpdkf2580 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말