글 읽기 - 시간초과 어떻게 해야하나요?

happy 7년 전 0

이게 시간초과가 납니다 .

한번 봐주세요 ㅎ

#include<cstdio>
using namespace std;

#define min(a,b) ((a)>(b) ? (b):(a))

int compare =100001;
int n, s;
int dap;
int i, j;
int main()
{
	int A[100001] = { 0, };

	scanf("%d %d", &n, &s);
	for (i = 0; i < n; i++) scanf("%d", &A[i]);

	for (i = 0; i < n; i++)
	{
		int sum = 0;
		for (j = i; j < n; j++)
		{
			sum += A[j];
			if (sum > s)
			{
				dap = j - i;
				dap = min(compare, dap);
			}
		}
	}
	printf("%d\n", dap);
}

hun222y 7년 전 0

10만*10만의 2중 포문이라서 .. O(n^2)의 복잡도인거 같아요.

알고리즘을 바꾸시는수 밖에 없을꺼같은데 ㅠㅠ dp를 활용해서 문제를 접근해 보세요ㅠㅠ

happy 7년 전 0

완탐문제인데 디피로 하는건가요?

hun222y 7년 전 0

음 ..방금 대충 짜보았는데 시간이 간당간당 하긴 하네요 . 저같은 경우에는 연산을 최소화 하기 위해서 처음에 입력받을떄 누적값들을 배열에 저장하고

각 배열에서 arr[i] - arr[j] 의 값이 정해진 (예 에서는 15)값을 넘을경우 dp배열에 i-j값을 넣어주는 방식으로 시간을 줄였습니다.

소스가 더러운점 이해하시고 봐보셔도 좋을꺼같아요 ㅠ

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#include<cstdlib>
#include<stack>
#include<cmath>
#include<queue>

using namespace std;


int arr[200000];
int dp[200000];

int main(){
    
    int num,val;
    cin >> num >> val;
    
    int sum = 0;
    for(int i=1;i<=num;i++){
        int a;
        cin >> a;
        sum+=a;
        arr[i] = sum;
    }
    for(int i=1;i<=num;i++){
        dp[i] = -1;
    }
//    
//    for(int i=1;i<=num;i++){
//        cout << arr[i] << " ";
//        
//    }cout <<endl;
    
    for(int i=1;i<=num;i++){
        for(int j=i-1;j>=1;j--){
            if(arr[i]-arr[j] > val){
                dp[i] = i-j;
                break;
            }
        }
    }
    
    int answer = 200000;
    for(int i=1;i<=num;i++){
        //cout << dp[i] << " ";
        if(dp[i]<answer && dp[i] != -1){
            answer = dp[i];
        }
    }
    if(answer == 200000){
        printf("0\n");
        return 0;
    }else
        printf("%d\n" , answer);
    
    
}

happy 7년 전 0

아하 좀 안써도 되는 헤더함수도 많이 적으셨네용 기본 틀인가요?ㅎㅎ

hun222y 7년 전 0

귀찮아서 복붙해여 ㅎㅎ

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

문제

문제

출처

ICPC

시간초과 어떻게 해야하나요?

happy 7년 전 0

hun222y 7년 전 0

happy 7년 전 0

hun222y 7년 전 0

happy 7년 전 0

hun222y 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말