[백준] 2631 줄 세우기 - Java

 

 

 

문제 출저

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

2631번: 줄세우기

 

 

 

문제 풀이

번호를 가진 아이들이 있습니다. 이 아이들을 번호 순서대로 줄을 세우려 할 때 이동해야 하는 최소한의 갯수를 구해야 합니다.

 

DP를 이용해 풀었습니다.

이동해야 하는 최소 갯수는 오름차순이 되지 않은 숫자들의 갯수 입니다.

예제의 경우를 보면 3 7 5 2 6 1 4 인데 이 때 가장 긴 오름차순의 길이는 3 5 6 으로 3 입니다.

그러면 나머지 숫자들의 자리를 바꿔주면 되므로 정답은 4가 되는 겁니다.

DP로 가장 긴 오름차순의 길이를 구하고 전체 길이에 그 값을 빼서 정답을 구했습니다.

 

 

 

소스 코드

package baekjoon.backjoon11.day0110.day07;

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

/*
줄 세우기
https://www.acmicpc.net/problem/2631

풀이 블로그
https://velog.io/@kjihye0340/%EB%B0%B1%EC%A4%80-2631%EC%A4%84%EC%84%B8%EC%9A%B0%EA%B8%B0Java
 */
public class B2631 {

  static int n;
  static int[] board;
  static int[] dp;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    board = new int[n];
    for(int i = 0; i < n; i++) {
      board[i] = Integer.parseInt(br.readLine());
    }

    dp = new int[n];
    dp[0] = 1;

    for(int i = 1; i < n; i++) {
      dp[i] = 1;
      for(int j = 0; j < i; j++) {
           if(board[i] > board[j]) {
             dp[i] = Math.max(dp[i], dp[j] + 1);
           }
      }
    }

    int answer = 0;
    for(int i = 0; i < n; i++) {
      answer = Math.max(answer, dp[i]);
    }

    System.out.println(n-answer);







  }
}