[백준] 11568번 : 민균이의 계략

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 LIS(최장 증가 수열) 문제로, 주어진 수열에 대해 각 자리까지의 가장 긴 수열의 길이를 DP에 저장하여 그 중 가장 큰 값을 찾는 방식으로 최장 증가 수열을 구할 수 있다.

1) 수열의 각 자리 수를 입력 받아 cards 배열에 저장한다.

2) dp 배열의 모든 자리를 1로 초기화 한다. (수열에 자기 자신만 있을 때의 크기)

3) 수열의 각 자리에 대해서 아래 과정을 반복한다.

• 현재 순서 원소를 모든 이전 원소들과 비교하며 아래 과정을 반복한다.
  • 해당 조건을 만족하는지 확인한다.
    • 현재 순서 원소가 이전 원소보다 크다.
    • 현재 순서 원소의 dp가 이전 원소의 dp + 1보다 작다.
  • 위 조건을 만족한다면 현재 순서 원소의 dp를 이전 원소의 dp + 1로 갱신한다.

4) 위 과정이 끝나면 dp에는 각 자리수까지의 가장 긴 수열이 저장 되어있고, dp에 저장된 값들 중 가장 큰 값이 최장 증가 수열이 된다.

🖥️ 풀이 코드

#include <iostream>

using namespace std;
int cards[1001];
int dp[1001];

int solution(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)			// 현재 순서 인덱스를 모든 이전 인덱스들과 비교
		{
			if (cards[j] < cards[i])		// 현재 인덱스의 값이 이전 인덱스의 값보다 클 때만 (증가 수열이므로)
			{
				if (dp[i] < dp[j] + 1)		// 현재 인덱스의 dp가 이전 인덱스의 dp + 1보다 작을 때만 갱신
					dp[i] = dp[j] + 1;
			}
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[i])
			max = dp[i];
	}
	return max;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> cards[i];
		dp[i] = 1;
	}
	cout << solution(n);
}