[BOJ - JAVA] 2631 - 줄세우기 (DP)

# 주소

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

2631번: 줄세우기

# 문제

 

# 문제 해설 및 코드 리뷰

package first;

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
        	arr[i]= scan.nextInt();
        }
        int[] dp = new int[n];
        dp[0] = 1;
        int count = 0;
        for(int i = 1; i < n; i++) {
        	dp[i] = 1;
        	for(int j = 0; j < i; j++) {
        		if(arr[i] > arr[j])
        			dp[i] = Math.max(dp[i], dp[j] + 1);
        	}
        	count = Math.max(count,  dp[i]);
        }
        System.out.println(n-count);
    }
}

처음엔 ArrayList로 접근해서 직접 배열을 옮겨가며 풀어보려고 했으나 생각해보니 LIS문제였습니다. 결국 이 배열을 순차적인 값으로 만드는 것이므로 이에 방해되는 값들을 찾아서 전체에서 빼준다면 우리가 원하는 값을 얻을 수 있습니다.

이중 for문을 열고 arr문을 직접 비교합니다. 이때 arr[i]와 arr[j]를 비교하는데 j의 범위는 i보다 작을 때로 설정합니다.

dp[i]의 값은 dp[i]와 dp[j] + 1의 값 중 큰 값을 dp[i]에 담습니다. 왜냐하면 dp의 모든 값은 1로 설정되어 있으므로 결국 dp[i]는 1을 의미하고 if문이 실행되어 dp[j]+1이 된다면 dp의 값은 저장되면서 1씩 증가하기 때문입니다.

그리고 예제에는 나오지 않아서 굳이 max값을 비교할 필요는 없지만 만약의 경우를 대비하여 count와 dp[i]를 비교하여 max값을 count에 담아 저장된 count를 n에서 빼주어 출력하면 최종적으로 끝납니다.

 

이 문제의 핵심은 LIS개념을 얼마나 잘 이해하고 있는지에 대한 것 같습니다.

LIS를 제대로 이해한다면 이분 탐색으로 푸셔도 딱히 손색은 없을 것이라 생각합니다. 

또한 예제를 잘 보시면 예제에서 힌트를 주고 있습니다. 잘 보시면 4, 7, 1, 2만 움직이고 있습니다. 이 숫자들을 제외하고 보면 3,5,6만그대로 있는데 이는 3,5,6이 LIS이고 전체 숫자 7개에서 3개를 빼면 그것이 이동횟수임을 알려주고 있습니다.

좀 더 문제를 보는 눈을 길러야 하겠습니다. 저도 열심히 공부해야겠네요. 시간이 꽤 걸려서 아쉽습니다.

감사합니다.