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

문제

길이가 N인 수열 A가 주어진다. 수열의 i번째 원소(Ai)로 끝나는 증가하는 부분 수열의 개수를 출력하는 프로그램을 작성하자.

단, 수가 너무 커질 수 있으니 998244353으로 나눈 나머지를 출력한다.

 

증가하는 부분 수열이 무엇인지 잘 모르는 친구들은 친절한 동원이가 준비한 아래 정의를 읽어보도록 하자.

• 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
• 증가하는 부분 수열이란 맨 처음 원소를 제외한 모든 원소가 바로 전 원소보다 큰 수열을 말한다. 다시 말해 길이가 N인 부분 수열 A가 있을 때, Ai−1<Ai (2≤i≤N) 를 만족하면 A는 증가하는 부분 수열이다.

동원이는 위 정의에 따라 길이가 1인 부분 수열은 항상 증가하는 부분 수열임에 주의하면 좋겠다는 메모를 추신으로 남겼다.

입력

첫째 줄에 수열의 길이 N이 주어진다.

둘째 줄에 N개의 정수 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 N개의 정수를 출력한다.

i번째로 출력하는 수는 Ai로 끝나는 증가하는 부분 수열의 개수를 998244353로 나눈 값이다.

제한

• 1≤N≤5000
• 1≤Ai≤5000

예제 입력 1 

5

1 2 3 4 5

예제 출력 1 

1 2 4 8 16

예제 입력 2 

5

1 1 1 1 1

예제 출력 2 

1 1 1 1 1

예제 입력 3 

5

1 2 2 4 3

예제 출력 3 

1 2 2 6 6

---

<Code>

//22971] 증가하는 부분 수열의 개수
#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int main(){
  freopen("input.txt", "rt", stdin);
  int n;
  scanf("%d", &n);
  vector <int> nums(n);
  vector <long long> res(n, 1);

  for(int i=0; i<n; i++){
    scanf("%d", &nums[i]);
  }

  for(int i=0; i<n; i++){
    for(int j=i; j>0; j--){
      if(nums[j-1]<nums[i]){
        res[i]+=res[j-1];
        res[i]=res[i]%998244353;
      }
    }
    printf("%lld ",res[i]);
  }
  
  return 0;
}

---

<Comment>

• 특정 값의 이전 숫자들을 하나씩 훑으면서,
• 작다면 1로 초기화된 배열에 누적으로 더함.

---

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

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