[백준, Java] 7570번, 줄 세우기(그리드, DP)

문제 링크

7570번: 줄 세우기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 어린이들을 번호 순으로 줄세우려고 합니다.

2. 어린이를 이동할 때에는 맨 왼쪽, 오른쪽으로 이동시킬 수 있습니다.

3. 어린이를 번호 순으로 줄 세우는 과정에서 최소 이동 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 어린이들이 이동할 수 있는 최선의 선택 및 중복된 탐색을 최소화하여 최소 이동횟수를 탐색합니다.

 

3. 탐색으로 얻은 어린이 최소 이동 횟수를 결과로 출력합니다.

 

어린이 이동 최선의 선택(그리디)

 

어린이의 움직임은 맨 왼쪽, 오른쪽으로만 이동할 수 있습니다.

 

 

어린이 이동하는 과정을 반복하면 연속하는 숫자들이 만나게 됩니다.

 

5

3

1

4

2

 

1 ~ 2의 연속하는 수가 만나게 되면서 이동하려면

 

5

1

4

2

3

 

5

1

2

3

4

 

1

2

3

4

5

이동한 어린이 : { 3, 4, 5 }

 

연속하는 어린이들을 움직이지 않으면 자연스럽게 연속하게 줄 세우기가 진행됩니다.

 

즉, 연속하는 수열의 최대 길이 이외에 어린이만 이동하면 자연스럽게 연속스러운 줄세우기가 완성됩니다.

 

전체 어린이의 수 - 가장 연속하는 수열의 길이 = 어린이 이동 최소 횟수

 

연속하는 수열의 최대 길이(DP)

 

어린이들의 연속하는 값들을 찾기 위해서 배열 완전 탐색을 반복할 수 있습니다.

 

하지만, 어린이 수의 최대가 1,000,000이기 때문에 N × N 의 시간복잡도를 가지면 시간 초과가 발생합니다.

 

어린이들의 번호를 탐색하면서 연속하는 수열의 길이를 구할 때에는 자신의 이전 어린이(-1)가 몇 명의 연속하는 수열의 길이를 가지고 있는지 알고 있으면 해당 값에 +1을 해주면 됩니다.

 

점화식으로 보면(n : 현재 어린이 번호)

 

DP[n] = DP[n-1] + 1

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

5

2

4

1

3

 

2. 어린이들이 이동할 수 있는 최선의 선택 및 중복된 탐색을 최소화하여 최소 이동횟수를 탐색합니다.

 

최대 연속하는 어린이 수열의 길이 구하기.

 

DP Table

 

0	1	2	3	4	5
0	0	0	0	0	0

 

5 2 4 1 3

 

DP[5] = DP[4] + 1 = 1

0	1	2	3	4	5
0	0	0	0	0	1

5 2 4 1 3

 

DP[2] = DP[1] + 1 = 1

0	1	2	3	4	5
0	0	1	0	0	1

5 2 4 1 3

 

DP[4] = DP[3] + 1 = 1

0	1	2	3	4	5
0	0	1	0	1	1

5 2 4 1 3

 

DP[1] = DP[0] + 1 = 1

0	1	2	3	4	5
0	1	1	0	1	1

5 2 4 1 3

 

DP[3] = DP[2] + 1 = 2

0	1	2	3	4	5
0	1	1	2	1	1

 

연속하는 수열 중 가장 긴 길이 : 2 ( 2, 3 )

 

 

3. 탐색으로 얻은 어린이 최소 이동 횟수를 결과로 출력합니다.

 

점화식을 통해서 어린이 최소 이동 횟수를 구하면

 

5(어린이 수) - 2(연속하는 어린이 최대 길이) = 3

 

3을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해서 어린이 번호 정보를 띄어쓰기 기준 나누었습니다.
• DP[]에 연속하는 수열의 길이를 저장하면서 최대 길이를 탐색합니다.
• 최대 길이와 어린이 수를 이용한 점화식으로 최소 이동 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] num = new int[n];
        //입력값 저장
        for(int i=0;i<n;i++){
            num[i] = Integer.parseInt(st.nextToken());
        }
        int[] DP = new int[n+1];
        int max = 0;
        //연속하는 수열의 최대 길이 탐색
        for(int i=0;i<n;i++){
            DP[num[i]] = DP[num[i]-1] + 1;
            max = Math.max(max,DP[num[i]]);
        }
        //점화식을 통한 어린이 이동 최소 횟수 BufferedWriter 저장
        bw.write(String.valueOf(n - max));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}