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

문제

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

분석

수열 A가 주어졌을 때, 각 i번째 숫자로 끝나는 증가하는 부분 수열의 개수를 구하는 문제이다.

모든 각 자리는 자신 1개로만 끝날 수 있기 때문에 최소 1가지의 경우를 가진다.
i가 끝나는 자리라고 고정하고 앞에 숫자들을 탐색했을 때, 자신보다 작은 경우라면 해당 위치까지 가능한 경우의 수를 더해준다.
계속 더하다보면 int 범위가 넘어가기 때문에 더할 때마다 998244353으로 나눈 나머지를 계산하여 오버플로우를 막아준다.

이중 for문을 사용했기 때문에 O(n^2)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] A;
    final static int MOD = 998_244_353;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] > A[j]) {
                    dp[i] = (dp[i] + dp[j]) % MOD;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            sb.append(dp[i]).append(" ");
        }
        System.out.println(sb);
        br.close();
    }
}