[백준/BOJ] 백준 16161번 : 가장 긴 증가하는 팰린드롬 부분수열

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

16161번: 가장 긴 증가하는 팰린드롬 부분수열

투 포인터를 이용하여 문제를 해결했다. right + 1이 right보다 크다면 증가하는 부분이므로 right를 오른쪽으로 옮겨가다가 right+1이 right보다 작은 구간을 만났을 때 right를 가운데로 하여 왼쪽과 오른쪽을 체크해 나아가는 방식으로 문제를 해결했다. 그리고 다음의 left와 right는 right+1 지점이 된다. right+1이 right와 같은 구간을 만났을 때는 right이하 부분을 왼쪽 부분, right+1 이상 부분을 오른쪽 부분으로 하여 체크해 나아가는 방식으로 문제를 해결했다. 그리고 다음의 left와 right는 right+1 지점이 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> s;
int result = 1;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		s.push_back(input);
	}

	int left = 0;
	int right = 0;

	while (1)
	{
		//right + 1이 없을때
		if (right >= s.size() - 1)
			break;

		//증가할때
		if (s[right] < s[right + 1])
		{
			right++;
		}

		//감소하는 구간일때 증가하는 펠린드롬이 어떤길이까지 만들어지는지 확인
		else if (s[right] > s[right + 1])
		{
			int len = 1;
			int check_left = right - 1;
			int check_right = right + 1;

			while (1)
			{
				if (check_left < left)
					break;
				if (check_right >= s.size())
					break;

				if (s[check_left] == s[check_right])
				{
					len += 2;

					check_left--;
					check_right++;
				}

				else
					break;
			}

			result = max(result, len);


			right++;
			left = right;
			right = right;
		}

		//같은 구간일때 증가하는 펠린드롬이 어떤길이까지 만들어지는지 확인
		else
		{
			int len = 0;
			int check_left = right;
			int check_right = right + 1;

			while (1)
			{
				if (check_left < left)
					break;
				if (check_right >= s.size())
					break;

				if (s[check_left] == s[check_right])
				{
					len += 2;

					check_left--;
					check_right++;
				}

				else
					break;
			}

			result = max(result, len);

			right++;
			left = right;
			right = right;
		}
	}

	cout << result;

	return 0;
}