Baekjoon/[3] DP

[백준] 11722번 가장 긴 감소하는 부분 수열 JAVA (자바) 풀이

Poorm 푸름 2024. 7. 1. 18:43

문제 11722번 (DP)

 :  수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램

 

    예) 수열 A의 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} , 길이 3

 

 

[입력]


 :  첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)

    둘째 줄에는 수열 A를 이루고 있는 Ai (1 ≤ Ai ≤ 1,000)

 

 

[출력]

 

 :  첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1. 브루트포스의 원리 이용하기

  • 시작지점 하나를 고정하고 나머지 지점들을 돌려가며 비교한다
    • dp[i] 로 시작지점고정
      모든 시작지점은 카운트 1값을 가진다
      현지점에서 수열을 세기 시작한다면 1이기 때문이다

  • 시작지점의 값과 이전 인덱스들의 값과 비교해서 더 큰 값 찾기
    • 시작지점(현위치) i  /  이전 인덱스(이전 위치) j
    • 큰 값부터 내려오는 것이기 때문에 이전에 더 큰 값이 있었다면
      arr[i]<arr[j]
    • 시작을 이전 인덱스로 변경후 카운트
      dp[j]+1
  • 비교가 끝난 후에는 최적의 값 dp배열 중에서 최종 max 값 찾기

 

예)  {10, 30, 10, 20, 20, 10}

  1. 시작지점 고정
    dp[3] = 1   /   arr[3] = 20 

  2. 시작지점 전의 인덱스들 모두 검사하는데 값이 더 큰 경우
    arr[0] ~ arr[2] 중에서 값이 더 큰 arr[1] = 30 찾았다

  3. 더 큰 값이 있으면 거기서부터 세는게 더 긴 수
    dp[3] = 1 < dp[1] + 1= 2
  • 최적의 dp중 최대값 출력

 

2. 11055번 가장 큰 증가하는 부분 수열문제와 다른점

  • 이건 합이 아닌 개수를 구하는 문제이다
    • 합일 경우 arr[i]를 더해줬으나 개수일 경우는 단순 카운트이기 때문에 +1 하기

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        int dp[] = new int[N];
        int result = 0;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        
        for(int i=0; i<N; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if(arr[i]<arr[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            result = Math.max(dp[i], result);
        }
        System.out.println(result);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[N];  dp 배열 초기화

    int arr[] = new int[N];  수열 담을 배열 초기화

    int result = 0;  결과 초기화
        
 :  StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());  수열 입력 받기
    }
        
  :  for(int i=0;i<N;i++){  
        dp[i] = 1;  어느 지점에서 세든 1 카운트하고 시작
            for(int j=0; j<i; j++){
               if(arr[j]<arr[i]){ 현지점보다 이전 인덱스 배열 값 중 더 큰 값이 있다면
                  dp[i] =Math.max(dp[i], dp[j]+1); 큰 값을 찾아 이전인덱스에서 시작 or 현위치 유지
               }
            }
            result = Math.max(dp[i], result);  최적의 값만 저장한 dp 배열 중 최대값 뽑기
     }


 :  System.out.println(result);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시