[BOJ] 22971 증가하는 부분 수열의 개수

최장 증가 부분 수열(LIS)의 갯수를 구하는 방법을 알아봅시다

0. 들어가기

문제 링크 : https://www.acmicpc.net/problem/22971
정답 코드 : http://boj.kr/39999426d2c14c229c43ca76f3f8488d

1. 문제 요약

길이가 $N$ 인 어떤 수열 $A_{1}$ , $A_{2}$ , ... $A_{N}$ 이 주어진다.

$A_{1}$ 에서 끝나는 증가하는 부분 수열의 갯수, $A_{2}$ 로 끝나는 증가하는 부분 수열의 갯수, ... $A_{N}$ 으로 끝나는 증가하는 부분 수열의 갯수를 각각 998,244,353으로 나눈 나머지를 공백으로 구분하여 출력한다.

증가하는 부분 수열이란, 원래 수열에서 1개 이상의 원소를 순서대로 선택하면서, 맨 처음 원소를 제외한 원소들은 바로 전 원소보다 커야 한다.

참고로, 길이가 1인 부분 수열은 증가하는 부분 수열이다.

1.1. 입력

$N$
$A_{1}$ $A_{2}$ ... $A_{N}$

$N$ : 수열의 길이, $1 \leq N \leq 5, 000$
$A_{i}$ : 수열의 원소들, $1 \leq A_{i} \leq 5, 000$

2. 풀이 정리

dp[i]는 $A_{i}$ 에서 끝나는 부분 수열의 개수를 저장한다.

dp[1]은 $A_{1}$ $A_{1}$ 에서 끝나는 부분 수열의 갯수이다.
- $A_{1}$ 로 증가하는 부분 수열을 만들 수 있으므로, dp[1]은 1이다.
dp[2]는 $A_{2}$ $A_{2}$ 에서 끝나는 부분 수열의 갯수이다.
- 우선 $A_{2}$ 만으로 증가하는 부분 수열을 만들 수 있으므로, dp[2]에 1을 저장한다.
- 만약 $A_{1} < A_{2}$ 이라면, $A_{1}, A_{2}$ 라는 증가하는 부분 수열을 만들 수 있다. 이 경우, dp[2] += dp[1]`이 된다.
dp[3]은 $A_{3}$ $A_{3}$ 에서 끝나는 부분 수열의 갯수이다.
- $A_{3}$ 만으로 증가하는 부분 수열을 만들 수 있으므로, dp[3]에 1을 저장한다.
- 만약 $A_{1} < A_{3}$ 이라면, $A_{1}, A_{3}$ 라는 증가하는 부분 수열을 만들 수 있다. 이 경우, dp[3] += dp[1]이 된다.
- 만약 $A_{2} < A_{3}$ 이라면, $A_{2}$ 로 끝나는 모든 증가하는 부분 수열 마지막에 $A_{3}$ 을 붙여 새로운 증가하는 부분 수열들을 만들 수 있다. 이 경우, dp[3] += dp[2]가 된다.
dp[i]는 $A_{i}$ $A_{i}$ 에서 끝나는 부분 수열의 갯수이다.
- $A_{i}$ 만으로 증가하는 부분 수열을 만들 수 있으므로, dp[i]에 1을 저장한다.
- $A_{1}$ ~ $A_{i - 1}$ 과 $A_{i}$ 를 비교해서, $A_{i}$ 가 큰 경우, 마지막에 $A_{i}$ 를 추가한 새로운 증가하는 부분 수열을 만들 수 있다.
- for j in (0..i-1): if A_j < A_i: dp[i] += dp[j]

출력은 998,244,353으로 나눈 나머지를 출력해야 하는데, dp[i]를 모두 구하고 나서 나머지를 구하면 dp[1] ~ dp[j]를 더하는 과정에서 오버플로우가 발생할 수 있다. 더하기 연산을 한 번 하면 나머지 연산을 바로 해줘서 오버플로우를 방지하자.

3. 구현

실제 구현은 0번 인덱스부터 사용하도록 했다.

#include <iostream>
using namespace std;

int N, A[5005];
int dp[5005];
int M = 998'244'353;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		dp[i] = 1;

		for (int j = 0; j < i; j++)
		{
			if (A[j] >= A[i]) continue;
			dp[i] += dp[j];
			dp[i] %= M;
		}
		cout << dp[i] << " ";
	}

	return 0;
}