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

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

Table Of Contents

0. 들어가기

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

2. 풀이 정리

dp[i]

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

 

출력은 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; }