백준 18353(병사 배치하기) - Python(파이썬) - LIS,다이나믹

18353번: 병사 배치하기

이와 LSI에 대한 설명 & 비슷한 문제

백준 11053( 가장 긴 증가하는 수열 ) - Python(파이썬),Java(자바)- 다이나믹(LIS)

풀이방법
① dp[i] 테이블을 생성한다 ( array[i]를 마지막 원소로 가지는 부분 수열의 최대 수열의 길이 )
② 점화식을 생성하면 모든 0<= j < i 에 대하여 D[i] = max( D[i] , D[i-1]+1) if array[ j  ] > array[ i ] 
③ 위 점화식을 활용하여서 for문으로 0부터 i-1까지 비교
④ 마지막에 열외해야하는 병사의 최소 수를 출력 전체 병사의 수에서 D[i]의 가장 큰 값을 빼기

풀이방법
① dp[i] 테이블을 생성한다 ( array[i]를 마지막 원소로 가지는 부분 수열의 최대 수열의 길이 )
② array.reverse()를 사용하여 반대로 만든 후 LIS 방식으로 하기
③ 점화식을 생성하면 모든 0<= j < i 에 대하여 D[i] = max( D[i] , D[i-1]+1) if array[ j  ] < array[ i ] 
④ 위 점화식을 활용하여서 for문으로 0부터 i-1까지 비교
⑤ 마지막에 열외해야하는 병사의 최소 수를 출력 전체 병사의 수에서 D[i]의 가장 큰 값을 빼기

Python(파이썬)인 경우:

import sys
N = int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))

dp=[1]*N

for i in range(0,N):
    for j in range(0,i):
        if array[i]<array[j]:
            dp[i]=max(dp[i],dp[j]+1)

print(N-max(dp))

import sys
N = int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))

#array 뒤집기
array.reverse()
dp=[1]*N

for i in range(1,N):
    for j in range(0,i):
        if array[i]>array[j] and dp[i]<dp[j]+1:
            dp[i]=dp[j]+1

print(N-max(dp))

import sys
N = int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))

#array 뒤집기
array.reverse()
dp=[1]*N

for i in range(1,N):
    for j in range(0,i):
        if array[i]>array[j]:
            dp[i]=max(dp[i],dp[j]+1)

print(N-max(dp))

 

Java(자바)인 경우 :

1) 반대로 하나씩 하기

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

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[] array = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            array[i]=Integer.parseInt(st.nextToken());
        }
        int[] dp=new int[N];
        for(int i=N-1;i>=0;i--){
            for(int j=N-1;j>=i;j--){
                if(array[i]>array[j] &&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int max=-1;
        for(int i=0;i<N;i++){
            max = dp[i]>max? dp[i]:max;
        }
        System.out.println(N-max-1);
    }
}