공부 128일차: 백준 11053번 가장 긴 증가하는 부분 수열 자바 java

11053 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

 

 

 

 

---

백준 11053번 문제 가장 긴 증가하는 부분 수열

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

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));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 디버깅 System.out.println(Arrays.toString(arr));
        
        // 첫번째 수부터 세보기
        int max = 0;
        int count = 0;
        for(int i = 0; i < n; i++) {
            if(max < arr[i]) {
                max = arr[i];
                count++;
            }
        }
        
        // 배열 2번째부터 끝까지 있는지 확인
        for(int i = 0; i < n; i++) {
            max = 0;
            int maxCnt = 0;
            for(int j = i+1; j < n; j++) {
                if(max < arr[j]) {
                    max = arr[j];
                    maxCnt++;
                }
            }
            
            if(count < maxCnt) {
                count = maxCnt;
            }
            
        }
        
        System.out.println(count);
    }
 
}
 

오답이니 과정 설명할 것 없이 바로 첨부하겠다

문제에 있는 예제 등을 입력하면 맞는 것처럼 보이지만,

6
90 30 40 150 50 60

같이 중간에 최대값이 끼어 있으면 원하는 대로 답을 얻을 수 없다 (이걸 왜 생각 못했지)

동적계획법으로 풀기 어려운 문제라고 생각해서 풀어 썼는데 틀렸다

 

https://st-lab.tistory.com/137

이 블로그 포함 여러 글을 읽어보니 말로만 들었던 LIS를 활용하는 문제였다

 

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

이런 식으로 수열의 길이를 dp로 두는 것이다

이는 어떻게 구할까?원하는 숫자에서 거꾸로 가면서, 그 arr[n]의 값보다 작은 값이 있다면 dp[n]과 그 해당 수 i의 LIS값에 1을 더하는 것이다

 

즉,20일 때 앞에 자신보다 작은 10이 있으므로 초기값 1과 10이 가진 dp값인 1+1 중 큰 2를 선택하고,

30일 때 앞에 자신보다 작은 20이 있으므로 초기값 1과 20이 가진 dp값인 2+1 중 큰 3을 선택하고,

.. 반복하여 50에서 4가 구해지는 격이다

수열에 해당할 때마다 그전 수의 수열 크기에 맞춰 +1을 해주는 것이 포인트

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] arr;
    static int[] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // n만큼의 수열크기 배열 구하기
        for(int i = 0; i < n; i++) {
            LIS(i);
        }
        
        long max = dp[0];
        for(int i = 1; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(max);
    }
    
    public static int LIS(int n) {
        
        // 확인한 적 없으면
        if(dp[n] == 0) {
            dp[n] = 1;    // 1로 초기화(자기 자신만 갖는 수열)
            
            for(int i = n-1; i >= 0; i--) {
                if(arr[i] < arr[n]) {
                    dp[n] = Math.max(dp[n], LIS(i)+1);
                }
            }
        }
        
        return dp[n];
    }
 
}
 

 

LIS를 써봤다는 것에 의의를 둬야겠다

 

 

---