[백준, JAVA] 11722번 : 가장 긴 감소하는 부분수열

seunguk noh·2023년 8월 8일
0

Algorithm

목록 보기
18/23

1. 문제

2. 아이디어

  • 처음에는 정렬을 해버렸는데.. 수열의 위치 자체가 의미 있는 값이기 때문에 현재 나열된 순서대로 해결해야 한다.

  • 현재 인덱스(i)의 값까지 감소하는 부분 수열의 길이를 정답 배열(i)에 담아두고 비교한다.

2-1. 다이나믹 프로그래밍

  • 문제를 더 작은 단위로 쪼개어, 작은 단계의 답을 활용하는 알고리즘
    작은 단위의 결과를 저장할 배열 등을 미리 만들어 저장해둔다.

  • Top - Down(재귀호출), Bottom-Up(반복문) 두 가지 접근이 존재한다.

3. 코드

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

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

4. 느낀점

  • 사실 알고리즘 개념을 봐서는 딱히 와닿지는 않았다... ㅎㅎ;
    몇가지 문제를 풀어보니 이런 상황이구나~ 싶긴 했다.

  • 정답을 위한 배열을 만들어두고, 재귀 혹은 반복문을 활용해서 이전의 값들과 비교한다! 라는 문제풀이 도구를 하나 얻었다.

4개의 댓글

comment-user-thumbnail
2023년 8월 8일

좋은 글 감사합니다. 자주 올게요 :)

1개의 답글
comment-user-thumbnail
2023년 8월 8일

이 문제 저는 어려웠어요..

1개의 답글