[백준/Baekjoon] 7570 줄세우기 C++ :: Dynamic Programming

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

7570번: 줄 세우기

---

1. Logic

- 줄세우기 문제는 최장 증가 부분 수열(LIS) 를 사용해서 풀이한다. 

LIS로 풀이하는 이유는 이미 순서대로 서있는 가장 많은 수를 제외한 나머지의 위치를 변경해주면 되기 때문이다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;

vector<int> vec;

int dp[1000001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int ans = -0x3f3f3f3f;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;

        dp[a] = dp[a - 1] + 1;
        ans = max(ans, dp[a]);
    }

    cout << n - ans;
}

---

 

 

3. Feedback

LIS를 떠올리긴 했지만 2차원 for문을 사용해서 풀었지만 당연히 시간복잡도가 터져서 틀렸다. 이전에 풀었던 문제는 나오는 숫자가 중복이 됐지만 이 문제는 중복이 없기때문에 들어오자마자 이전에 들어옸던 수를 확인해서 숫자를 올려주어 확인해서 풀었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐