[C/C++] 백준 - 2491번 : 수열

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

2491번: 수열

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

 

다른 문제들보다 DP문제는 내가 왜 이 문제를 이렇게 풀었을까, 어떻게 이 방법을 생각했을까를

다시 한 번 생각해보는게 중요한 것 같다.

 

우선 이 문제의 시간제한은 1초, 최대 N은 100,000

-> 그럼 완전탐색으로 모든 경우의 수를 확인한다면? : 시간 제한 내 통과가 어렵다

그렇기 때문에 O(n) 또는 O(nlogn)의 방법으로 해결해야한다.

 

그럼 어떻게 해결할까?

-> 처음 : 투포인터로 이상 또는 이하의 경우의 수를 따져보는건 어떨까? : 이상의 경우 하나만 존재하거나

이하의 경우 하나만 따질때에는 효과적일 수 있으나 2개의 경우를 모두 고려해야하기때문에 까다로움. 구현은 할 수 있을 거 같긴한데, 더 나은 방법이 존재할 거 같다.

-> 그럼 동적계획법의 메모이제이션으로 이어서 나아가는 방식으로 하면 될 거 같다. 근데 투포인터처럼 이상 또는 이하의 경우 모두 구현해야하나? : 2차원 배열 형식으로 이상의 경우와 이하의 경우를 함께 따져 1개의 for문으로 해결이 가능할 거 같다. 그렇다면 시간복잡도도 O(n)이므로 통과가 가능하다.

 

위 과정으로 생각해서 구현했고 맞았다.

2차원 배열로 이상의 경우 또는 이하의 경우 모두 구해주면서 최대값을 저장해주는 방식이다.

#include <iostream>
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

int N;
int arr[100002];
int dp[100002][2];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
}

int solution() {
	int answer = 1;
	dp[0][0] = 1; // 작아지는 거
	dp[0][1] = 1; // 커지는 거
	for (int i = 1; i < N; i++) {
		dp[i][0] = dp[i][1] = 1;
		if (arr[i - 1] <= arr[i]) dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1);
		if (arr[i - 1] >= arr[i]) dp[i][0] = max(dp[i][0], dp[i - 1][0] + 1);
		answer = max({ answer, dp[i][0], dp[i][1] });
	}
	return answer;
}

int main() {
	CUNLINK;
	Input();
	cout << solution();
	
	return 0;
}