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

0. 들어가기

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

1. 문제 요약

길이가

인 어떤 수열 , , ... 이 주어진다.

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

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

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

1.1. 입력

N

A_1

A_2

...

A_N

• N
  : 수열의 길이,
  1 \le N \le 5,000
• A_i
  : 수열의 원소들,
  1 \le A_i \le 5,000

2. 풀이 정리

dp[i]는

에서 끝나는 부분 수열의 개수를 저장한다.

• dp[1]은
  A_1
  에서 끝나는 부분 수열의 갯수이다.
  • A_1
    로 증가하는 부분 수열을 만들 수 있으므로, dp[1]은 1이다.
• dp[2]는
  A_2
  에서 끝나는 부분 수열의 갯수이다.
  • 우선
    A_2
    만으로 증가하는 부분 수열을 만들 수 있으므로, dp[2]에 1을 저장한다.
  • 만약
    A_1 \lt A_2
    이라면,
    A_1, A_2
    라는 증가하는 부분 수열을 만들 수 있다. 이 경우, dp[2] += dp[1]`이 된다.
• dp[3]은
  A_3
  에서 끝나는 부분 수열의 갯수이다.
  • A_3
    만으로 증가하는 부분 수열을 만들 수 있으므로, dp[3]에 1을 저장한다.
  • 만약
    A_1 \lt A_3
    이라면,
    A_1, A_3
    라는 증가하는 부분 수열을 만들 수 있다. 이 경우, dp[3] += dp[1]이 된다.
  • 만약
    A_2 \lt A_3
    이라면,
    A_2
    로 끝나는 모든 증가하는 부분 수열 마지막에
    A_3
    을 붙여 새로운 증가하는 부분 수열들을 만들 수 있다. 이 경우, dp[3] += dp[2]가 된다.
• dp[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;
}