[JAVA] 1965번 - 상자넣기 (최장 증가 부분 수열)

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

DP문제를 풀때마다 최장부분수열? 뭐 이런문제를 몇번 봤는데 이해를 못했었다.

DP의 기포를 다지는데 자주 사용되는 예제라고 해서 따로 공부했다.

https://sskl660.tistory.com/89

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

이분블로그를 참고했다. 진짜 이해가 바로된다!!!! 

 

시간복잡도

O(N^2)이다 O(1,000,000) 으로 시간내에 충분히 가능하다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 입력을 받는다 

2. LIS에 맞게 for문돌린다 

3. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

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());
        String[] input = br.readLine().split(" ");

        int dp[] = new int[n];
        int arr[] = new int[n];
        
        for(int i=0; i<n; i++) {      
        	arr[i]=Integer.parseInt(input[i]);     	    	
        }
        
     
       
        int ans = 0;
        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);
        		}
        	}
        	ans = Math.max(dp[i], ans);
        }
        System.out.println(ans);

        
    }	
}