글 읽기 - 3015번 스택 문제 관련 도움 부탁드립니다.

bshg1111 5년 전 0

제가 푼 소스가 틀렸다는데 어디가 문제인지 확인이 잘 안되서요...

케이스를 많이 돌려보진 않았지만 정답소스와 답은 동일하게 나오는거 같긴한데

어지간하면 혼자 찾아보겠는데 하다가 잘 안되서 글 남겨봅니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX 500000
int N;
int S[MAX+1];
long long ans;
int stack[MAX+1];
int sp;

void input_data()
{
	int i;
	scanf("%d", &N);
	for(i=1; i<=N; i++)
		scanf("%d", &S[i]);
}

long long solve()
{
	int i, j;
	long long res = 0;
	
	for(i=1; i<=N; i++)
	{
		if(sp==0)
		{
			stack[++sp] = S[i];
			//printf("stack : [%d]\n", stack[sp]);
		}
		else
		{
			if (stack[sp] < S[i])
			{
				while(1)
				{
					if (sp == 0 || stack[sp] > S[i]) break;
					//printf("pair : [%d:%d]\n", stack[sp], S[i]);
					sp--;
					res++;
				}
				
				if(sp != 0)
				{
					res++;
					//printf("pair : [%d:%d]\n", stack[sp], S[i]);
				}
				stack[++sp] = S[i];
				//printf("stack : [%d]\n", stack[sp]);
			}
			else
			{
				if(stack[sp] == S[i])
				{
					j = sp;
					while(1)
					{
						j--;
						res++;
						//printf("pair : [%d:%d]\n", stack[sp-1], S[i]);
						if (j == 0 || stack[j] > S[i]) break;
					}
				}

				res++;
				//printf("pair : [%d:%d]\n", stack[sp], S[i]);
				stack[++sp] = S[i];
				//printf("stack : [%d]\n", stack[sp]);
			}
		}
	}
	
	return res;
}

int main()
{
	input_data();
	ans = solve();
	printf("%lld", ans);
	return 0;
}

djm03178 5년 전 4

매우 작은 케이스들에서도 반례가 나옵니다.

2
3
3
output: 2
correct answer: 1

2
1
1
output: 2
correct answer: 1

4
4
4
1
2
output: 5
correct answer: 4

bshg1111 5년 전 0

덕분에 반례 하나는 발견했네요 도움 감사합니다!

그래도 문제가 남은거 같은데 좀 더 찾아봐야겠네요

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

문제

문제

출처

ICPC

3015번 스택 문제 관련 도움 부탁드립니다.

bshg1111 5년 전 0

djm03178 5년 전 4

bshg1111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말