글 읽기 - c++ 제발 반례좀 부탁드립니다.지금까지 반례 전부 통과 됩니다.

wldlf94 2년 전 0

게시판 반례 + 스스로 만든 반례 다 해봤는데 전부 값 잘 나오는데 왜 틀렸다고 할까요..
반례 좀 부탁드립니다. 고수님들

다시 봐도 완벽한데 도대체 왜..

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using std::cout; using std::cin;
using std::vector;

int H, W;
int answer;


// monotone stack 알고리즘 이용.

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	std::stack<int> st;
	cin >> H >> W;

	int max = 0;
	
	while (W--) {
		int h;
		cin >> h;

		int cnt = 0;
		int p = h; // h를 p에 넣고    p를 사용.
        
		while (!st.empty() && st.top() < h) { 
			if (p > max){  // 왼쪽 max 높히보다 높을때
				if (st.top() == max) {//바로 전 단계에서 max까지 물 받아졌으면, 
					st.pop();
                    continue;
				}
				else {
					p = max; //  4 3     <--
				}           //  3 0 1 4  <-- 와 같은 경우 때문에
			}
			answer += p - st.top();
			st.pop();
			cnt++;
		}
		if (cnt) {//answer에서 빗물 계산 했으면, 스택에 다시 채워줌.
			for (int i = 0; i < cnt; i++) {
				st.push(p);
			}
		}
		max = std::max(max, p);
		st.push(p);	
	}
	cout << answer;

	return 0;
}

bnb2011 2년 전 3

반례 드립니다.

5 5
1 0 3 2 4
    
// Output: 1
// Answer: 2

wldlf94 2년 전 0

와 감사합니다. 꾸벅 :) 덕분에 해결했습니다.!!

진짜 반례 찾는다고 복잡한거 20개 정도는 더 해본거 같은데 간단한 반례가 숨어있었군요..

wldlf94 2년 전 0

반례를 디버깅 해보면서 while 문 안을 아래와 같이 바꿨습니다.

if (h > max && st.top()<=max) {

answer += max - st.top();

st.pop();

}

else {

answer += h - st.top();

st.pop();

cnt++;

}

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

문제

문제

출처

ICPC

c++ 제발 반례좀 부탁드립니다.지금까지 반례 전부 통과 됩니다.

wldlf94 2년 전 0

bnb2011 2년 전 3

wldlf94 2년 전 0

wldlf94 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말