글 읽기 - 반례 좀 찾아주세요

pulsar5813 7년 전 0

Stack 이용해서 푸는 방식으로 했는데...

왜 틀렸다고 나오는지 잘 모르겠어요ㅠ

#include <iostream>

using namespace std;

class Component {
    public :
        int height;
        long long int value;
        Component* next;
    Component(int h, long long int v, Component* n) {
        height = h;
        value = v;
        next = n;
    }
};


Component* top;
int stackSize;
long long int maxValue;


void push(int h, long long int v) {
    if(stackSize == 0) top = new Component(h, v, NULL);
    else {
        Component* tmp = new Component(h, v, top);
        top = tmp;
    }
    stackSize++;
}

void pop() {
    if (stackSize == 0) return;
    else {
        Component* tmp = top;
	top = top->next;
        delete[] tmp;
        stackSize--;
        return;
    }
}

void checkStack() {
	int t = stackSize;
	Component* tmp = top;
	while(t != 0) {
		t--;
		cout<<"tmp next is not NULL and Component stored h is "<<tmp->height<<endl;
		tmp = tmp->next;
	}
	return;

}

void buildHistogram(int h) {
    if(stackSize == 0) push(h, h);
    else {
        if(h >= top->height) push(h, h);
        else {
            int numOfPop = 0;
	    int justPop = 0;
            while((stackSize != 0)&&(top->height >= h)) {
                if(top->height*numOfPop + top->value > maxValue) 
                    maxValue = top->height*numOfPop + top->value;
		justPop = top->value;
                pop();
                numOfPop++;
            }
	    push(h, h*numOfPop + justPop);
        }
    }
    return;
}

int main(void) {
    long long int ans[100000];
    int ptr = -1;
    while(true) {
        int input;
        cin>>input;
	//cout<<"input size is "<<input<<endl;

        if(input == 0) break;
        else {
	    ptr++;
            stackSize = 0;
            maxValue = 0;
            top = NULL;
            int h;
            for(int i=0; i<input; i++) {
                cin>>h;
                buildHistogram(h);
		//cout<<"currently pushed h value is "<<h<<endl;
		//checkStack();
            }
        
            if(stackSize == 0) ans[ptr] = maxValue;
            else {
                 buildHistogram(-1);
                 ans[ptr] = maxValue;
	    }
	}
    }

    for(int i=0; i<=ptr; i++) 
	   cout<<ans[i]<<endl;
    
    return 0;
}

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

문제

문제

출처

ICPC

반례 좀 찾아주세요

pulsar5813 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말