백준(BOJ) 11568 민균이의 계략 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/11568

11568번: 민균이의 계략

풀이에 이용된 알고리즘 및 개념: LIS, DP, 이진 탐색(?)

 

어디선가 들어본 부분 증가 수열 문제구나... 주어진 수열의 가장 첫 원소만 있을 때의 LIS, 두번째 원소까지 있을 때의 LIS, 세번째까지 있을 때의 LIS... 뭔가 이전 결과들 중에 지금 확인하고 있는 원소를 하나 추가해주면 될 것 같은데... 등등의 아주 다량의 사고의 흐름이 있었다.

 

예전부터 이런 문제를 보면 "아 LIS 문제 같은데....."라는 생각을 하게 되어서 이참에 다시 개념 정립을 했다.

 

LIS에 대한 설명은 다른 분들의 아주 뛰어난 정리 및 설명이 있어서 본인이 참고한 페이지를 첨부한다.

 

https://shoark7.github.io/programming/algorithm/3-LIS-algorithms

LIS의 길이를 구하는 3가지 알고리즘

https://jason9319.tistory.com/113

[최장 증가 수열] LIS(Longest Increasing Subsequence)

 

DP와 lower_bound를 이용한 두 가지 코드를 하기에 첨부한다.

 

개인적으로는 lower_bound 풀이가 조금 더 깔끔?한 것 같고 STL을 활용한다는 점에서 공부할 때 재미있었던 것 같다.

 

/* BOJ 11568 민균이의 계략 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n, arr[1001], dp[1001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> arr[i], dp[i] = 1;
 
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
 
    cout << ans << endl;
 
    return 0;
}

 

/* BOJ 11568 민균이의 계략 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n, arr[1001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    vector<int> ans;
    const int INF = 1e9;
    ans.push_back(-INF); // 절대적으로 작은 수 하나 삽입
 
    for (int i = 1; i <= n; i++)
    {
        if (arr[i] > ans.back())
            ans.push_back(arr[i]);
        else
        {
            // arr[i]가 들어갈 위치 찾기
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), arr[i]);
            *it = arr[i];
        }
    }
 
    cout << ans.size() - 1 << endl; // 처음 삽입한 -INF 제거
 
    return 0;
}