[SWEA] 3307. 최장 증가 부분 수열 D3 JAVA (자바) 풀이

문제 3307. 최장 증가 부분 수열 (DP)

 

수열 : { A1, A2, ... , AN }

최장 증가 부분 수열 : { B1, B2, ... , BK }  (0≤K≤N, B1 < B2 < ... < BK)

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

[입력]

: 첫 번째 줄 테스트 케이스의 수 T

: 각 테스트 케이스의 첫째 줄에 수열의 길이 N(1≤N≤1,000)
  둘째 줄에는 수열의 원소 N개 ( 1 ≤ N  ≤ 2³¹-1 자연수)

[출력]

 ‘#T’ 최대 증가 부분 수열의 길이 출력

 

 

 [과정]

 

초기 방식) 시작점을 하나씩 고정하면서 다음 노드로 순차적으로 돌면서 수가 더 크면 길이를 count 하는 방식으로 완전탐색을 사용했지만 시간초과가 나거나 오류가 떠서 방식을 dp로 변경했다

 

최장 증가부분 수열 (LIS)에는 주로 DP나 이분탐색을 이용해라 !

 

 

DP - 보텀업 (상향식) 방식사용

• 가장 흔하게 사용되는 DP 접근법
• 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 계산하여 저장
  
  
• end: 끝지점
• node: 시작점
• dp[end] : 길이
• 예) arr =[3, 10, 2, 11]

 

외부 for문 (end)	내부 for문 (node < end)	dp [end]	if문 조건1 arr[node] < arr[end]	if문 조건2 dp[end] < dp[node] + 1	실행 dp[end] = dp[node] + 1
0	0  <  0	dp[0] = 1	-
1	0  <  1	dp[1] = 1	3  < 10   참	dp[1] < dp[0] + 1 참	dp[1] = 2
2	0  <  2	dp[2] = 1	3  <  2  거짓	-
2	1  <  2	dp[2] = 1	10  <  2  거짓	-
3	0  <  3	dp[3] = 1	3  <  11  참	dp[3] < dp[0] + 1 참	dp[3] = 2
3	1  < 3	dp[3] = 2	10  <  11  참	dp[3] < dp[1] + 1 참	dp[3] = 3
3	2  <  3	dp[3] = 3	2  <  11  참	dp[3] < dp[2] + 1 거짓	-

확실히 브루트포스 보다는 가볍게 돌지만 정확히 dp를 어떻게 사용하는지 너무 어렵다 

 

 

실패 코드_브루트포스

 

import java.util.*;
import java.io.*;

class Solution {
    static int arr[], n;
    static int result;

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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

            result = 0;
            for(int i = 0; i < n; i++) {
                int count = 1; // 현재 원소부터 시작하는 부분 수열의 길이
                for(int j = i + 1; j < n; j++) {
                    if(arr[j] > arr[i]) {
                        count++; // 다음 원소가 현재 원소보다 크면 카운트 증가
                    }
                }
                result = Math.max(result, count);
            }

            System.out.println("#" + test_case + " " + result);
        }
    }
}

 

 

 [코드]

import java.util.*;
import java.io.*;
 
class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for(int test_case = 1; test_case <= T; test_case++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int arr[] = new int[n];
            int dp[] = new int[n];
            int result = 1;
             
            for(int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
 
            for(int end=0; end<n; end++) {
            dp[end] = 1; 
                for(int node=0; node<end; node++) {
                    if(arr[node] < arr[end] && dp[end] < dp[node] + 1) {
                    dp[end] = dp[node] + 1;
                    }
                }
            result = Math.max(result, dp[end]);
            }
            System.out.println("#"+test_case+" "+result);
        }
    }
}

 

 

 [해설]
     

 :  for(int test_case = 1; test_case <= T; test_case++) {

            int n = Integer.parseInt(br.readLine());  수열 개수

            StringTokenizer st = new StringTokenizer(br.readLine());  

            int arr[] = new int[n];  수열 담기

            int dp[] = new int[n];  길이 담기

            int result = 1;  자기자신까지는 길이 1이니까 초기값 1로 설정

             

            for(int i = 0; i < n; i++) {  수열 입력 받기

                arr[i] = Integer.parseInt(st.nextToken());

            }

 

            for(int end=0; end<n; end++) {  끝지점 정하고 시작

                dp[end] = 1;  자기자신 길이 1

                for(int node=0; node<end; node++) { 시작 지점 이동 끝지점까지만

                    if(arr[node] < arr[end] && dp[end] < dp[node] + 1) {  1. 이전 수보다 클 것 

                        dp[end] = dp[node] + 1;                                            2. 현재 길이(1) 포함 했을 때보다 작다면 갱신

                    }

                }

            result = Math.max(result, dp[end]);  끝지점 기준 결과 최대값으로 갱신

            }

            System.out.println("#"+test_case+" "+result);  출력

    }

      

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

SW Expert Academy

 

 

 

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