[JAVA] 백준 q2631 - 줄세우기

2631번: 줄세우기

 

---

의식의 흐름

이전에 풀었던 가장 긴 증가하는 수열(https://monicajo074.tistory.com/44)을 사용하면 될 것 같은뎅..?

일단 가장 긴 증가하는 수열을 구한 다음에 해당 수열 안에 들어가지 못한 아이들만 옮기면 그게 최소인 경우일 것 같다.

 

풀이 과정

1.  아이들의 수(N)을 입력 받는다.

2. 현재 서있는 순서를 배열(nums)에 담고 증가하는 수열의 길이를 담을 배열(dp)를 1로 초기화한다.

for(int i=0;i<N;i++){
    nums[i] = Integer.parseInt(br.readLine());
    dp[i] = 1;
}

3. 현재 번호(nums[i])와 뒷쪽 번호(nums[j])를 비교하면서 dp를 채워간다.
> 자세한 풀이는 2023.10.16 - [알고리즘/백준] - [JAVA] 백준 q11053 - 가장 긴 증가하는 부분 수열

4. 아이들의 수(N) - 가장 긴 증가하는 수열의 길이(maxCnt)를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int N; // 아이들의 수
    public static int[] nums; // 현재 서있는 순서
    public static int[] dp; // 증가하는 수열의 길이

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        dp = new int[N];
        for(int i=0;i<N;i++){
            nums[i] = Integer.parseInt(br.readLine());
            dp[i] = 1;
        }

        int maxCnt = 0; // 가장 긴 증가하는 수열의 길이
        for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
                if(nums[i]<nums[j]){
                    dp[j] = Math.max(dp[j], dp[i]+1);
                    maxCnt = Math.max(maxCnt, dp[j]);
                }
            }
        }

        bw.write(Integer.toString(N-maxCnt));
        bw.flush();

        br.close();
        bw.close();
    }
}