[BOJ] 14659 한조서열정리하고옴ㅋㅋ

(2021년 3월 4일에 작성한 글입니다.)

14659번: 한조서열정리하고옴ㅋㅋ

 

처음에는 O(n^2) 풀이밖에 안 떠올랐는데 어떻게 하는거지? 하다가

신촌 연합 캠프 초급 스터디 멘토 할 때

효규가 강의자료 만든 거 보고

그리디구나! 했다

​

근데 처음에 제출할 때 틀렸는데, 그 이유는

맨 마지막 결과에 대한 업데이트를 해줘야 하기 때문이다

​

예를 들어

5

5 4 3 2 1

이런 인풋이 들어오면

처음에 제출한 코드에서는 답이 0이 될 것이다

​

이를 해결하는 방법은 두 가지가 있는데

1. 매 번 ans를 ans = max(ans, cnt)로 업데이트 하거나

2. 반복문 종료 후 마지막으로 ans = max(ans, cnt)로 ans 업데이트 하거나

이다.

​

이런 실수 하지 말자.

const int NMAX = 202020;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	int cnt = 0, ans = 0;

	int cur;
	cin >> cur;
	n--;
	while (n--) {
		int temp; cin >> temp;
		if (cur > temp) cnt++;
		else {
			cur = temp;
			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);

	cout << ans;

	return 0;
}