글 읽기 - 시간초과 해결좀요 ㅠㅠ

vhxpffltm 7년 전 0

전체 탐색형식으로 했는데 어떻게 해야 할까요 ㅠ

#include<stdio.h>
#include<algorithm>
#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int main()
{
	int K, arr[100010] = { 0 },sum=0;
	cin >> K;
	for (int i = 0; i < K; i++) {
		scanf("%d", &arr[i]);
		if (arr[i] == 0) {
			for (int j = i-1; j >= 0;j--){
				if (arr[j] != 0) {
					arr[j] = 0;
					break;
				}
			}
		}
	}
	for (int i = 0; i < K; i++)
		sum += arr[i];
	printf("%d", sum);
}

petil777 7년 전 0

작성하신 코드의 시간복잡도는 O(n^2)입니다. 따라서 n이 10만까지 가능한 이 문제의 경우 위의 방법으로 푸시면 당연히 시간초과가 발생합니다.

자료구조 stack을 찾아보시면 도움이 될 것입니다.

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

vhxpffltm 7년 전 0

감사합니다~~ 해결했습니다

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

문제

문제

출처

ICPC

시간초과 해결좀요 ㅠㅠ

vhxpffltm 7년 전 0

petil777 7년 전 0

vhxpffltm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말