BOJ_2631

😄 최근에 비슷한 문제를 풀어서 그런가. 보고 끄적끄적하다가 어떻게 풀어야할지 딱 알아냈다.

💻 2631 : 줄세우기

• 규칙을 찾아내야 한다.
• 1~N 까지의 아이들을 오름차순으로 정렬해줘야 한다.
• 12345로 아이들이 서있을 때는 굳이 정렬을 시켜주지 않아도 되지만 54321로 서있을 때는 총 다섯번의 아이들을 움직여줘야 정렬이 완료된다.
• 혹시 판단이 서는가??? 바로 가장 큰 증가하는 부분수열이다.
• 이 수열은 Dynamic Programming으로 풀어줘야 한다.

DP

for (int i = 0; i < N; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if(v[i] > v[j] && dp[i] < dp[j] + 1)
            {
                dp[i] = dp[j] + 1;
            }
        }
        result = max(result, dp[i]);
    }

• dp[i]는 1로 초기화해줘야 자기보다 앞에있는 번호들을 탐색하다가 작은수가 존재하지 않아도 1로 설정이 가능하다.
• v[i] > v[j] : 자기 자신이 앞에 있는 수보다 커야 증가하는 수열
• dp[i] < dp[j] + 1 : 자기 자신의 dp 수량보다 앞 수의 dp 수량+1이 더 많아야 가장 큰 증가하는 수열!!
• for문을 나가서 또 for문을 돌려주면 비효율적이므로 max값을 바로바로 그 즉시 구해버린다.

💻 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

int N, result = 0;
vector<int> v;
int dp[201];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N;i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
    for (int i = 0; i < N; i++)
    {
        dp[i] = 1;
        for (int j = i - 1; j >= 0; j--)
        {
            if(v[i] > v[j] && dp[i] < dp[j] + 1)
            {
                dp[i] = dp[j] + 1;
            }
        }
        result = max(result, dp[i]);
    }
    cout << N - result << endl;
}

😜 해결방법만 알면 금방 풀어낼 수 있는 문제다. 그래서 그런지 정답률이 높다!! 필자는 운이 좋게도?? 보자마자 어떻게 풀어야할지 감을 잡아서 빠르게 풀어낼 수 있었다.