글 읽기 - 이 문제를 시간초과안 뜨려면 어떻게 해야 하나요????????

bangbadak 5년 전 0

지금까지 한 25번은 해본 것 같은데... 대부분이 시간초과 아니면 틀렸다고 나오네요...

코드보고 어느게 문제점인지 알려주세요.....

다 답이 잘 나오기는 하는데 시간을 어떻게 줄일 수 있을까요?

#include<iostream>
using namespace std;
int main(void)
{
	int N, S, i, j, s = 0, e = 0, num[100000] = { 0, }, cnt = 0, endcnt = 0, sum = 0;
	cin >> N >> S;
	for (i = 0; i < N; i++)
		cin >> num[i];
	for (i = 0; ; i++)
	{
		for (j = s, sum = 0; j < e + 1; j++)
			sum += num[j];
		if (sum == S)
		{
			cnt++;
			s++;
			endcnt++;
		}
		else if (sum > S)
		{
			s++;
			endcnt++;
		}
		else
			e++;
		if (endcnt > N - 1)
			break;
	}
	cout << cnt;
	system("pause");
}

djm03178 5년 전 2

11~12번째 줄처럼 하지 말아야 합니다. sum을 매번 초기화하고 전부 s부터 e까지 다 더해야 할까요? 예를 들어, s~e의 sum이 x였다면 s~e+1까지의 sum은 x+num[e+1]인데 x를 재계산할 필요가 있을까요?

jh05013 5년 전 1

시간 복잡도에 대해 공부해 보세요.

bangbadak 5년 전 0

흠 고쳐보긴 했는데. 틀렸다고 나오네요..

반례가 뭐가 있을까요?

#include<iostream>
using namespace std;
int main(void)
{
	int N, S, i, s = 0, e = 0, num[100000] = { 0, }, cnt = 0, endcnt = 0, sum = 0;
	cin >> N >> S;
	for (i = 0; i < N; i++)
		cin >> num[i];
	sum += num[0];
	for (i = 0; ; i++)
	{
		
		if (sum == S)
		{
			sum -= num[s];
			cnt++;
			e++;
			s++;
			endcnt++;
			sum += num[e];
		}
		else if (sum < S)
		{
			e++;
			sum += num[e];
		}
		else
		{
			sum -= num[s];
			s++;
			endcnt++;
		}
		if (endcnt > N - 1)
			break;
	}
	cout << cnt;
	system("pause");
}

djm03178 5년 전 1

애초에 문제 이해를 잘못하신 것 같습니다. 아래 예시의 답은 1입니다.

10 10
10 10 10 10 10 10 10 10 10 10

bangbadak 5년 전 0

아 그러네요;;

제가 문제에서 요구하는 값을 잘못봤네요;;

감사합니다.

bangbadak 5년 전 0

만약에 S가 0이면 뭘 출력해야되는 건가요??

djm03178 5년 전 0

0 < S니까 그런 입력은 주어지지 않습니다.

bangbadak 5년 전 0

반례좀 찾아주실 수 있나요...

현재 60번째 시도중...

#include<iostream>
using namespace std;
int main(void)
{
	bool f = false;
	int N, S, i, s = 0, e = 0, num[100000] = { 0, };
	int endcnt = 0, sum = 0, cnt = 100000;
	cin >> N >> S;
	for (i = 0; i < N; i++)
		cin >> num[i];
	sum += num[0];
	for(i = 0; ; i++)
	{
		if (i >= N * N / 2)
			break;
		if (sum == S)
		{
			if (cnt > e - s + 1)
				cnt = e - s + 1;
			if (f == false)
				f = true;
			sum -= num[s];
			e++;
			s++;
			endcnt++;
			sum += num[e];
		}
		else if (sum < S)
		{
			e++;
			sum += num[e];
		}
		else
		{
			if (cnt > e - s + 1)
				cnt = e - s + 1;
			if (f == false)
				f = true;
			sum -= num[s];
			s++;
			endcnt++;
		}
		if (endcnt > N - 1)
			break;
	}
	if (f == false)
		cnt = 0;
	cout << cnt;
	system("pause");
}

djm03178 5년 전 0

N이 약 5만 이상이 되면 14번째 줄의 N * N은 오버플로우를 일으킵니다.

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

문제

문제

출처

ICPC

이 문제를 시간초과안 뜨려면 어떻게 해야 하나요????????

bangbadak 5년 전 0

djm03178 5년 전 2

jh05013 5년 전 1

bangbadak 5년 전 0

djm03178 5년 전 1

bangbadak 5년 전 0

bangbadak 5년 전 0

djm03178 5년 전 0

bangbadak 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말