🌱 문제 링크
https://www.acmicpc.net/problem/2631
📝 풀이 과정
풀이
문제 유형 : DP
이 문제는 어린이들을 정렬해야 하는 문제이다.
중요한 건 이미 순서를 지키고 있는 어린이들은 옮길 필요가 없다. 예를 들어, 12435 순서대로 서있다면 1245 인 어린이들은 위치를 바꿀 필요가 없고 3 어린이만 위치를 바꾸면 된다. 이를 풀기 위해 필요한 개념이
LIS(Longest Increasing SubSequence) 알고리즘이다.
가장 긴 증가하는 부분 수열인데, 말 그대로 수가 증가하는 부분수열 중에 가장 긴 수열을 구하는 알고리즘이다.
이 수를 구해서 전체 인원수에서 빼면 최소로 이동하는 어린이의 수가 나온다.
시간 복잡도 : O(n^2)
* LIS 알고리즘
ex) 12435라면
1. 1->2->4->3->5 순서대로 반복을 돌림
2. 처음엔 자기 자신 1개이므로 dp에 1 을 저장
3. 처음부터 자기 자신 직전까지 숫자를 비교하며 자기가 더 크다면 ( 증가한다. ) dp 에 저장된 값을 비교한다.
4. 현재 dp에 저장된 수보다 비교 숫자의 dp+1값이 더 크다면 갱신한다. (증가하는 숫자가 더 많다.)
5. 반복문을 모두 돌았다면 dp 에 저장된 값들 중에 가장 큰 값이 LIS 값이다.
느낀점
이런 방식의 풀이과정은 어떻게 생각해내는건지 모르겠다...
💻 코드
import java.io.*;
import java.util.*;
/*
* 어린이들을 정렬하는 문제
* 이미 제자리에 있는 어린이들은 위치를 바꿀 필요가 없음
* LIS(Longest Increasing SubSequence)를 구해서(=제자리에 있는 어린이들) 전체 인원수에서 빼면 이동할 어린이의 수
*/
public class Main_bj_2631_줄세우기 {
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("res/input_bj_2631.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 전체 인원 수
int[] children = new int[N];
for(int i=0; i<N; i++) {
children[i] = Integer.parseInt(br.readLine());
}
int[] dp = new int[N]; // LIS
int max=0;
for(int i=0; i<N; i++) {
dp[i] = 1;
for(int j=0; j<i; j++) {
if(children[j] < children[i]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(N-max);
br.close();
}
}
|
cs |
📌 채점 결과
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[BOJ] 1593. 문자 해독 - JAVA (0) | 2022.07.03 |
---|---|
[BOJ] 14725. 개미굴 - JAVA (0) | 2022.06.20 |
[BOJ] 17143번. 낚시왕 - JAVA (0) | 2022.04.09 |
[BOJ] 13460번. 구슬 탈출 2 (0) | 2022.04.08 |
[BOJ] 15961번. 회전초밥 - JAVA (0) | 2022.04.07 |