99클럽 코테 스터디 31일차 TIL (미들러): [백준][Java] 2631 줄세우기 - 골드4

 

문제 보기

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

 

 

풀이

어제와 동일한 제일 긴 부분 수열 찾기 이다.

그런데 문제로부터 이 방법을 생각해 내는 게 쉽지 않았다.

이미 완성되어 있는 수열은 그대로 두고 잘못 된 자리에 가 있는 애들을 옮겨준다고 생각해보자!

 

 

전체 코드

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

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    int[] dp = new int[N];
    int max = 0;
    for (int i = 0; i < N; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      max = Math.max(max, dp[i]);
    }

    bw.write(N - max + "");
    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2631.%E2%80%85%EC%A4%84%EC%84%B8%EC%9A%B0%EA%B8%B0