백준 BOJ 22971 - 증가하는 부분 수열의 개수

N이 그리 크지 않아서

O(N^2) 풀이를 적용할 수 있다.

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

22971번: 증가하는 부분 수열의 개수

심지어 문제에서 친절하게 점화식 짜는거까지 도와준다

dp[i]를 Ai로 끝나는 증가하는 부분 수열의 개수로 정의하면

dp[i]를 1로 초기화 해두고,

(0<=j<i) 인 j 에대해서 Aj < Ai일때 부분수열을 그대로 이어받아 확장할수 있게 되니

+=연산자로 적당히 더해주면 된다.

 

#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
typedef long long int ll;

int A[12345] = {0};
ll dp[12345] = {0}; 

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	for(int i=0; i<12345; i++) dp[i] = 1;
	
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> A[i];
	}
	
	for(int i=1; i<N; i++){
		for(int j=0; j<i; j++){
			if(A[j] < A[i]){
				dp[i] += dp[j];
				dp[i] %= MOD;
			}
		}
	}
	
	for(int i=0; i<N; i++){
		cout << dp[i] << " ";
	}
	return 0;
}

/*
N^2가 되네욤 ㄴㅇㅅ
dp[i] : Ai로 끝나는 증가하는부분수열의 개수
dp[i] = 1로 초기화 
dp[i] = for(int j=0; j<i; j++)에 대해서
if(Aj < Ai){
	dp[i] += dp[j]
} 
*/

깔끔하게 AC