[백준 7570] - 줄 세우기(JAVA)[골드3]

문제

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

7570번: 줄 세우기

문제 풀이

접근방법에 대해서 정말 난감했던 문제였다.

맨 앞과 뒤로만 접근을 할 수 있다..? ->  Dequeue를 써야 해서 옮겨줘야 하나?라고 생각했었다.

하지만 손으로 경우의수를 만들어서 계산을 해보니 이전에 풀었던 문제와 비슷한 느낌이 들었다.

https://jja2han.tistory.com/368

[백준 2631] - 줄 세우기(Kotlin)[골드4]

문제 이름까지 똑같을줄은 몰랐는데 정말 비슷한 문제가 있었고, 이번 문제도

가장 길게 증가하는 수열을 찾아서 그 길이만큼 아이들의 수를 빼면 될 것 같았다.

초기 코드

   public static void solution() {
        int max_length = 0;
        int count;
        while(!q.isEmpty()){
            int now = q.poll();
            count=0;
            while(!q.isEmpty() && now<q.peek()){ //q가 비지 않고, 처음으로 q보다 작은 원소가 나오면 종료
                count++;
                now = q.poll();
            }
            max_length = Math.max(max_length,count);
        }
        System.out.println(n-1-max_length);
    }

q에 입력받은 아이들의 순서를 넣고 queue가 빌 때까지 반복했다.

 

q에서 계속해서 하나씩 꺼내서 증가하는 수열의 길이를 측정했다.

now를 계속해서 변경해 주면서 안쪽의 while문을 반복했다.

그러다 반복문이 끝나면 길이를 업데이트하고, 다시 반복했다.

이렇게 할 경우 증가하는 부분 수열의 길이를 구할 수 있었고, 정답일 것이라고 예상했지만 틀렸었다.

 

그러다 다른 예외케이스를 계속해서 구하다가

1 4 3 2 5를 해봤다.

위의 순열에서 가장 길게 증가하는 수열의 길이는 {1,4,5} {1,3,5} or {1,2,5}인 3이다.

하지만 손으로 직접 해보면 3이라는 결과를 얻을 수 없었다.

 

4 2 1 3 5

      ⬇️

1 4 2 3 5

      ⬇️

1 2 3 5 4

      ⬇️

1 2 3 4 5

 

분명히 우리가 구했던 가장 길게 증가하는 수열의 길이는 3이고, 5명이니까 2명만 움직이면 된다고 생각을 했지만,

결과는 3명을 움직여야 한다.

즉 접근 방법이 잘못된 것이다.

 

분명히 [2631] 줄 세우기는 이렇게 풀렸는데, 왜 해당 문제는 풀리지 않는 걸까 생각을 해봤다.

차이점은 다음과 같다.

해당 문제는 아이들의 순서를 바꾸는 위치가 맨 앞, 맨뒤로 한정되어 있다는 사실이었다.

따라서 우리는 연속적으로 가장 길게 증가하는 수열을 구하고, 해당 부분을 제외하고 나머지를 옮겨줘야 한다.

4 2 1 3 5를 예로 들면, 가장 길게, 그리고 연속적으로 증가하는 수열은 {2,3}이 될 것이다.

따라서 위에서 손으로 해봤던 것처럼 {2,3}을 제외한 {1,4,5}가 이동한 것이다.

 

그러면 이제 우리는

가장 길게, 그리고 연속적으로 증가하는 수열의 길이를 구해야 한다.

변경된 코드

추가적인 배열을 통해서 앞에 나보다 앞에 있어야 할 어린이가 있는지 검사를 했다.

dp [idx]는 번호가 연속된 아이들의 길이이다.
 초기값은 0이다.

   public static void solution() {
        while (!q.isEmpty()) {
            int now = q.poll();
            if (dp[now - 1] == 0) { //아직까지 어린이가 나오지 않았다면
                dp[now] = 1;
            } else {
                dp[now] = dp[now - 1] + 1;
            }
        }
        for(int i=1; i<=n; i++){
            answer = Math.max(answer,dp[i]);
        }
    }

dp 배열을 통해서 now인 어린이 앞에 어린이가 나왔는지 찾는다.

만약 dp값이 0이라면 now보다 뒤에 있기 때문에 1을 넣어준다.

만약 0이 아니라면 앞에 어린이가 존재했다는 뜻이기 때문에 해당 값에다가 +1을 해준다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static long answer = 0;
    static Queue<Integer> q = new LinkedList<>();

    static int[] dp;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        solution();
        System.out.print(n - answer);
    }

    public static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            q.add(Integer.parseInt(st.nextToken())); 
        }
    }

    public static void solution() {
        while (!q.isEmpty()) {
            int now = q.poll();
            if (dp[now - 1] == 0) { //아직까지 어린이가 나오지 않았다면
                dp[now] = 1;
            } else {
                dp[now] = dp[now - 1] + 1;
            }
        }
        for(int i=1; i<=n; i++){
            answer = Math.max(answer,dp[i]);
        }
    }
}