[TIL] 99클럽 코테 스터디 30일차 TIL + 백준 1965 상자 넣기

 

문제 풀이

 

문제 탐색하기

이 문제는 DP 알고리즘을 활용하여 풀 수 있는 문제입니다.

문제 유형은 백준의 '11722 가장 긴 감소하는 부분 수열' 문제와 비슷하므로 아래의 링크에 해당 문제에 대해 정리한 게시글을 남겨두겠습니다.

https://coding-babo.tistory.com/173

[TIL] 99클럽 코테 스터디 27일차 TIL + 백준 11722 가장 긴 감소하는 부분 수열

 

DP 알고리즘을 통해 문제 풀이를 구현해 보자면 아래와 같습니다.

1. int 배열을 선언해서 상자의 크기를 저장해줍니다.
2. DP 배열을 선언하여 시작을 1로 세팅합니다.
3. 현재 값의 이전 값들을 비교해서 현재 값보다 이전 값이 작다면 현재의 dp 배열의 값과 이전의 dp 배열의 값 + 1을 비교하여 더 큰 값으로 현재 dp 배열의 값을 재세팅 해줍니다.
4. 탐색이 종료되면 dp 배열 중 최대 값을 출력해줍니다.

 

문제 풀이

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 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];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        for(int i=1; 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);
                }
            }
        }

        int max = 0;
        for(int a : dp){
            max = Math.max(a, max);
        }

        System.out.println(max);
    }
}