[BOJ] 백준 2631 줄 세우기 (문제풀이, 코드 c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 백준의 2631번 문제 줄 세우기 문제입니다.

 

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

 

중복 없는 연속된 수들을 최대한 적게 숫자를 이동시켜 오름차순으로 정렬하는데 그 때의 이동횟수를 구하는 문제 입니다.

 

 

 

해결 과정

 

이 문제를 해결하는데는 다음과 같은 요소를 알아야합니다.

 

증가하는 부분수열 중 가장 큰 것을 구하고 부분수열에 해당되는 않는 숫자들을 옮기면 가장 적은 횟수로

정렬이 가능하다는 것 입니다.

 

문제에서 사용된 예시입니다.

 

3 7 5 2 6 1 4

 

증가하는 부분수열 중 가장 큰 것 { 3, 5, 6 } 이 숫자들은 고정해둔 채

나머지 7, 2, 1, 4를 움직이는 것 입니다.

 

그렇기에 답은 7 - 3 = 4가 됩니다.

 

증가하는 부분수열 중 가장 큰 것을 구하기 위해선

문제의 특성 상 N이 200으로 작아 brute force 방식으로 접근하여도 괜찮습니다.

 

 

이중 반목문으로 첫 인덱스로 전체를 순회할 때 현재 인덱스(i)가 이전의 인덱스(j) 보다 크고

위 조건에 성립되는 이전의 인덱스 중 증가하는 부분수열의 크기가 가장 큰 것의 값을 가져와 1을 더한 값을

i번 째 증가하는 부분수열의 크기로 최신화 시킵니다.

 

 

 

코드 전문

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[202];
int origin[202]; 

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) 
        cin >> origin[i];

    int ans = -1;
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; --j) 
            if (origin[i] > origin[j] && ((dp[j]+1) > dp[i])) 
                dp[i] = dp[j]+1;
        
        ans = max(ans, dp[i]);
    }

    cout << n - ans;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

 

DP를 사용해야한다는 느낌은 들었지만 증가하는 부분수열에 대한 부분이 빠르게 떠오르지 않았습니다.

많이 배운 것 같습니다. 감사합니다.

 

 

 

참고한 글 

 

https://yabmoons.tistory.com/197

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.