[백준(BOJ)] 2631번 : 줄세우기 - C++[CPP]

www.acmicpc.net/problem/2631

2631번: 줄세우기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

배치하는 문제를 만났을 때, 가장 중요한 포인트는 기준이다.

기준을 잡고 풀이를 하면 훨씬 편하다.

 

그렇다면 이 문제에서는 기준을 어떻게 잡는 것이 좋을까?

정답은 오름차순으로 정렬하라고 하였으니 오름차순으로 가장 길게 정렬된 부분을 기준으로 하자

 

만약 LIS(최장 부분 증가수열)을 알고 있다면 문제를 더 편하게 풀 수 있다.

 

문제에서 주어진 예제를 통해 기준을 살펴보자

3 7 5 2 6 1 4

위 배열에서 기준은 3,5,6이다. 오름차순으로 정렬되어있고 가장 길다.

그렇다면 우리는 이제 3,5,6을 두고 나머지 4개의 수를 이동하여 정렬하기만 하면 된다.

LIS CODE는 아래 문제 풀이에 있다.

 

 

---

⊙ LIS(최장 부분 증가수열)

 

앞에서부터 뒤로, 각각의 값이 이전 값보다 크고 가장 긴 부분 수열을 뜻한다.

예를 들어, {3, 7, 5, 2, 6, 1, 4}의 증가하는 부분 수열은 다음과 같다.

{3, 7}, {3, 5}, {3, 5, 6}, {2, 4}, {1, 4} 등등....

 

여러 가지가 있지만 그중에서 가장 긴 배열이 LIS이다.

 

위 예에서 LIS는 {3, 5, 6}이다.

 

---

 

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N,result=0;
    scanf("%d",&N);

    int arr[N],dp[N];
    for(int i=1;i<=N;i++) {
        scanf("%d",&arr[i]);
    }

    for (int i = 1; i <= N; i++) {  //LIS
		dp[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[j] < arr[i] && dp[i] <= dp[j])
				dp[i] += 1;
        result = max(result, dp[i]);
	}
    printf("%d",N - result);
}

 

---

⊙ 결과

 

---

 

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!