[백준] 알고리즘 2491번 - 수열 문제

문제

www.acmicpc.net/problem/2491

2491번: 수열

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, ansup = 1, ansdown = 1, lenup = 1,lendown=1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	
	for (int i = 2; i <= n; i++) {
		if (arr[i] >= arr[i - 1]) {
			lenup++;
		}
		else {
			ansup = max(ansup, lenup);
			lenup = 1;
		}
		if (arr[i] <= arr[i - 1]) {
			lendown++;
		}
		else {
			ansdown = max(ansdown, lendown);
			lendown = 1;
		}
	}
	ansup = max(lenup, ansup);
	ansdown = max(lendown, ansdown);
	int ans = 0;
	ans = max(ansup, ansdown);
	cout << ans;
}
 

풀이

아무생각없이 LIS , LDS 문제인줄 알고 삽질하다가 다시 생각해보니 그냥 단순히 하나의 배열을 하나씩 비교해주면서 길이를 저장하면 되는 문제였다.

이는 연속된 양옆의 숫자들을 비교하기만 하면되닌깐 간단하게 해결할 수 있는거 같다.

 

마지막에 ansup과 ansdown을 len들과 다시 비교하여 정답을 새로운 변수에 저장하여 출력하였다.

이를 생략하면 90%정도에서 실패하였다고 뜨는데 분명 무슨 반례가 있을 것이다..

이 반례는 저도 잘 모르겠네요

알아보고 추가하도록 하겠습니다.

 

앞으로는 정답출력을 새로 한다음 출력하는 습관을 가져야겠습니다.