백준 - 줄세우기 2631

백준에서 "줄세우기" 문제에 대한 풀이를 담고 있습니다.

 

백준 - 줄세우기 2631

 

 

블로그 목차

 

1. 코드

2. 원리

추천글

 

 

코드

 

- 아무리 생각해도 풀이를 떠올리기가 힘들었고, 풀이를 찾다가 그 풀이에서 도입부분의 설명만 듣고 바로 이해를 해버렸다.

- 정답률이 66%였는데, 코드가 어렵다기 보다는 그 아이디어를 찾는 것이 어려운 문제였다고 생각한다.

- 일단 어떤 수들이 나열되어 있는데, 우리가 몇 개의 수를 옮겨서 적절하게 정리를 하려면 어떻게 움직일까?

 

- 바로, 이미 정렬되어 있는 부분들은 제외하고, 나머지 부분들을 이동시켜서 정렬하게 될 것이다.

- 이런 비슷한 생각을 떠올렸는데, 나는 무조건 다닥다닥 붙어있는 경우만을 생각해서 정답에 도달하지 못했다.

- 예를 들어, 3, 7, 5, 2, 6, 1, 4 로 숫자가 나열되어 있다면, 이미 정렬되어 있는 부분은 다음과 같다.

1) 3, 7

2) 3, 5, 6

3) 5, 6

4) 2, 6

5) 2, 4

5) 1, 4

 

- 우리는 최소한의 수들만 움직여야 하니까 2번과 같이 3, 5, 6을 고정시켜 두고 나머지 수들을 움직이게 될 것이다.

- 그렇기 때문에 수의 갯수 7에서 고정된 수 3개를 빼면 4개의 수가 남고, 4개의 수만 움직이므로 정답 역시 4가 된다.

 

- 이 문제를 풀기 위해선 DP가 필요하다.

- dp[i]의 의미는 0~i까지의 부분 배열에서 정렬된 가장 큰 부분 수열의 길이를 가지고 있다.

- 여기서 중요한 점은 dp 배열은 모두 1로 초기화 되어 있어야 하는데, 나 혼자서도 1이라는 길이의 부분 수열이기 때문에 0으로 초기화를 해두면 안된다.

- 조금 풀이를 덧붙이면 아래와 같다.

 

- i - 1번째 수부터 0까지 탐색을 하며 i번째 수보다 작은 수를 찾는다.

- 찾은 수의 index가 j라면, dp[j]에서 j번째 수를 기준으로 만들어질 수 있는 정렬된 가장 큰 부분 수열의 길이를 가지고 온다.

- 거기에 내가 포함되어야 하므로 dp[j] + 1이 dp[i]의 값이 될 수 있다.

- 하지만, 최대가 되어야 하기 때문에 또 다른 i보다 작은 수 k를 계속 찾는 식으로 탐색을 이어 나간다.

- 그 중에서 가장 최대가 될 때를 찾아 dp[i]에 담는다.

 

- 아래는 코드인데,, 이번에는 자바다 ㅋㅋㅋㅋㅋㅋㅋ

코드

 

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {

    int N;
    int[] array;
    int[] dp;
    public void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        array = new int[N];
        for (int i = 0; i < N; i++)
            array[i] = Integer.parseInt(bf.readLine());
    }

    public void solution() throws IOException{
        dp = new int[N];
        Arrays.fill(dp, 1);
        for (int i = 1; i < N; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (array[j] < array[i]) {
                    if (dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (dp[i] > max)
                max = dp[i];
        }
        System.out.println(N - max);
    }
    public void solve() throws IOException{
        input();
        solution();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}

 

앞으로 정말 많은 코테 전형들이 나를 기다리고 있을텐데, 항상 잘 풀 수 있을까 무섭다..

추천글

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