백준2491 - 수열

https://www.acmicpc.net/problem/2491

2491번: 수열

연속되어 증가하는 가장 긴 수열을 구하거나 연속되어 감소하는 가장 긴 수열의 길이를 구하는 문제이다. 다이나믹 프로그래밍을 이용하여 푼다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;

int main() {
	int n; //수열의 길이
	int num; //수열의 각 원소
	int big = 0, small = 0; //현재까지 가장 큰 숫자, 현재까지 가장 작은 숫자
	int d1[MAX] = { 0, }; //x번 숫자 일 때 증가 수열의 길이
	int d2[MAX] = { 0, }; //x번 숫자 일 때 감소 수열의 길이
	int ans = -1; //가장 긴 증가 수열이거나 가장 긴 감소수열의 길이

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num;
		if (i == 1) { //첫번째 원소이면
			//각 수열의 길이를 1로 설정
			d1[1] = 1;
			d2[1] = 1;

			//각각의 가장 큰 숫자와 가장 작은 숫자를 처음 숫자로 설정
			big = num;
			small = num;
		}
		else { //그 외의 경우
			if (big <= num) { //현재 입력한 숫자가 가장 큰 숫자보다 크면
				big = num; //현재 숫자를 가장 큰 숫자로 교체하고
				d1[i] = d1[i - 1] + 1; //직전 수열에서 +1을 하여 현재 길이를 증가시킨다.
			}
			else { //그 외의 경우
				big = num; //현재 숫자를 가장 큰 숫자로 교체하고
				d1[i] = 1; //현재 길이를 1로 설정
			}
			if (small >= num) { //현재 입력한 숫자가 가장 작은 숫자보다 작으면
				small = num; //현재 숫자를 가장 작은 숫자로 교체하고
				d2[i] = d2[i - 1] + 1; //직전 수열에서 +1 하여 현재 길이를 증가시킨다.
			}
			else { //그 외의 경우
				small = num; //현재 숫자를 가장 작은 숫자로 교체하고
				d2[i] = 1; //현재 길이를 1로 설정
			}
		}

		//현재 위치에서 가장 긴 숫자를 구한다.
		ans = max(ans, d1[i]);
		ans = max(ans, d2[i]);
	}

	cout << ans;
}