[백준] 11722 - 가장 긴 감소하는 부분 수열 (JAVA)

1. 소요시간 : 5분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 2
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/11722
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

같은 날 푼 문제중에 이와 90% 똑같은 문제가 있어서 금방 풀 수 있었다. 그 문제와 풀이 방법이 흡사하므로 여기서는 문제 풀이 방법을 자세하게 적지는 않겠다.
그 문제를 푼 풀이는 https://velog.io/@anwlro0212/백준-11055-가장-큰-증가하는-부분-수열JAVA 이다.
이 문제는 거의 40분 가까이 걸렸었다.

3. 풀이과정

1. dp[i] 를 1로 초기화 한다.
2. j는 i+1 부터 탐색을 시작.
3. arr[i] 가 arr[j] 보다 크다면 dp[j]의 값을 갱신한다.

시간복잡도는 이중 for문으로 O(n^2) 이 걸린다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		
		int n=Integer.parseInt(br.readLine());
		int dp[]=new int[n+1];
		int arr[]=new int[n+1];
		st=new StringTokenizer(br.readLine());
		
		for(int i=1;i<arr.length;i++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		Arrays.fill(dp,1);
		
		for(int i=1;i<dp.length;i++) {
			for(int j=i+1;j<dp.length;j++) {
				if(arr[i]>arr[j])
					dp[j]=Math.max(dp[i]+1,dp[j]);
			}
		}
		int max=0;
		for(int i=1;i<dp.length;i++)
			max=Math.max(max,dp[i]);
		
		System.out.println(max);
		
		
		
	}
}

5. 결과

6. 회고

비슷한 문제를 풀었는데 시간이 짧게 나온 것으로 보아서 이 유형에 어느정도는 익숙해진 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212