글 읽기 - 반례를 못찾겠습니다...

wondy1128 7년 전 0

출력초과 오류시엔 다른 분들이 NO의 경우에 + or -를 출력하면 안된다고 해서 수정하였습니다.

#include<cstdio>

class stack{
private:
	int data[100001];
	int cnt, ansCnt;
	bool ansFalse;
	char ans[200000];
public:
	stack(){
		cnt = 0;
		ansCnt = 0;
		bool ansFalse = true;
	}
	void push(int i){
		data[cnt++] = i;
		ans[ansCnt++] = '+';
	}
	int pop(){
		if(!empty()){
			ans[ansCnt++] = '-';
			//printf("%d ",data[cnt-1]);
			return data[--cnt];			
		}else{
			ansFalse = false;
		}
	}
	bool empty(){
		if(cnt==0) return true;
		return false;
	}
	bool getAnsFalse(){
		return ansFalse;
	}
	int getAnsCnt(){
		return ansCnt;
	}
	char getAns(int i){
		return ans[i];
	}
	void setAnsFalse(bool i){
		ansFalse = i;
	}
};

int main(){
	stack s;

	int t, cnt = 0, num = 1;
	int input[100000] = {0};
	scanf("%d", &t);
	
	for(int i = 0 ; i < t ; i++){
		scanf("%d",&input[i]);
	} // input data

	while(true){
		if(cnt == t){ // 입력한 갯수와 테스트의 크기가 같다면 종료
			break;
		}// end
		
		if(input[cnt] == num){ // 입력받은 인덱스에 위치한 값과, num가 같다면
			
			s.push(num++);		// 넣고
			s.pop();					// 꺼냄
			cnt++;					// 다음 인덱스로
			
		}else if(input[cnt] < num){ // 입력받은 인덱스에 위치한 값보다 num이 더 크다면, 꺼내기

			int temp = s.pop(); // 꺼냄			
			if(temp != input[cnt]){ // 꺼낸 값이 입력받은 인덱스에 위치한 값과 같지 않다면
				s.setAnsFalse(false);	// NO를 출력하기위해 false 값 설정
				break;						    // end
			}
			cnt++;		// 맞는 경우라면 다음 인덱스 값 진행

		}else{ // 입력받은 인덱스에 위치한 값보다 작다면 그대로 푸쉬

			s.push(num++); // 푸쉬			
		}		
	}

	if(s.getAnsFalse()){
		int temp = s.getAnsCnt();
		for(int i = 0 ; i < temp ; i++){
			printf("%c\n",s.getAns(i));			
		}
	}else{
		printf("NO\n");
	}
	return 0;
}

zlzmsrhak 7년 전 0

예제가 반례인 것 같습니다..?

wondy1128 7년 전 0

예제는 잘동작합니다!

zlzmsrhak 7년 전 0

http://ideone.com/8K4Ka4

저는 항상 no만 나와서 이상한데 코드 달라진거나 undefined behavior가 없는지 확인해보세요

wondy1128 7년 전 0

여기 부분만 지나면 계속 false로 바뀌어버리는데 비주얼스튜디오랑 컴파일러가 좀 다른건가요??

첫 초기화가 제대로 되지 않아서 왜인지 되지 않아서 클래스 인스턴스 변수 선언이후에 s.setAnsFalse(true); 로 설정하면 정상구동되는 것은 확인했습니다! 감사합니다!

#include<cstdio>
 
class stack{
private:
	int data[100001];
	int cnt, ansCnt;
	bool ansFalse;
	char ans[200000];
public:
	stack(bool t){
		cnt = 0;
		ansCnt = 0;
		bool ansFalse = t;
	}
	void push(int i){
		data[cnt++] = i;
		ans[ansCnt++] = '+';
	}
	int pop(){
		if(!empty()){
			ans[ansCnt++] = '-';
			//printf("== %d\n", data[cnt-1]);
			return data[--cnt];			
		}
	}
	bool empty(){
		if(cnt==0) return true;
		return false;
	}
	bool getAnsFalse(){
		return ansFalse;
	}
	int getAnsCnt(){
		return ansCnt;
	}
	char getAns(int i){
		return ans[i];
	}
	void setAnsFalse(bool i){
		ansFalse = i;
	}
};
 
int main(){
	stack s(true);
 
	int t, cnt = 0, num = 1;
	int input[100000] = {0};
	scanf("%d", &t);
 
	for(int i = 0 ; i < t ; i++){
		scanf("%d",&input[i]);
	} // input data
	printf("\n==%s\n",s.getAnsFalse()? "true" : "false");
	while(true){
		if(cnt == t){
			printf("\n%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			break;
		}// end
		printf("\n<1>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
		 printf("\n<213123>%d==%s\n",input[cnt], s.getAnsFalse()? "true" : "false");
		if(input[cnt] == num){
			//printf("equal %d\n",num);
			printf("\n<2-0>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			s.push(num++);
			printf("\n<2-1>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			int i = s.pop();
			printf("\n<2-2>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			//printf("%d\n",i);
			printf("\n<2-3>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			cnt++;		
			printf("\n<2-4>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
 
		}else if(input[cnt] < num){
			int temp = s.pop();
			//printf("%d %d",temp, input[cnt]);
			if(temp != input[cnt]){
				s.setAnsFalse(false);
				printf("%d %d \n",temp,input[cnt]);
 
				break;
			}
			printf("\n<3>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
			cnt++;		
		}else{
			//printf("not equal %d\n",num);
			s.push(num++);
			printf("\n<4>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
 
		}	
		printf("\n<5>%d==%s\n",num, s.getAnsFalse()? "true" : "false");
	}
	printf("\n%d==%s\n",num, s.getAnsFalse()? "true" : "false");
	if(s.getAnsFalse()){
		int temp = s.getAnsCnt();
		for(int i = 0 ; i < temp ; i++){
			printf("%c\n",s.getAns(i));			
		}
	}else{
		printf("NO\n");
	}
 
 
	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...

wondy1128 7년 전 0

zlzmsrhak 7년 전 0

wondy1128 7년 전 0

zlzmsrhak 7년 전 0

wondy1128 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말