백준 7570 c++ "줄 세우기" -PlusUltraCode-

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

[필자 사고]

재미난 문제다. 처음에 LIS로 접근해서 N-size형태로 문제를 해결하려 했지만 놓친 부분이 있다.

원하는 위치에 넣는게 아닌 앞 혹은 뒤로만 넣을 수 있다는 조건이다.

이 조건으로 인해 LIS는 불가능하다.

우리가 찾아야 할 것은 연속된 가장 킨 숫자들의 갯수다.

해당 갯수를 찾은 뒤 N-size형태로 하면 답을 구할 수 있다.

처음 best 값을 1로 초기화 해야한다. 실수하지 말자.

 

아래는 자세한 코드 해설이다.

[코드 해설]

줄 세우기 실패 (백준 2631) 풀이 및 코드 해설

이 문제는 **“제일 앞이나 제일 뒤로만 이동시켜 번호 순서대로 정렬하는 최소 횟수”**를 구하는 문제입니다.
입력은 1부터 N까지의 번호가 섞여 있으며, 가능한 최소 이동 횟수를 출력해야 합니다.

---

1. 문제 핵심 개념

이동 규칙을 보면, 한 번에 할 수 있는 행동은 다음 두 가지뿐입니다.

1. 어떤 어린이를 맨 앞으로 보내기
2. 어떤 어린이를 맨 뒤로 보내기

이때 중요한 점은, 남겨진 어린이들의 상대적 순서는 유지된다는 것입니다.
즉, “움직이지 않아도 되는 어린이들”은 **원래 줄에서의 순서가 올바른 번호 순서(오름차순)**여야 합니다.

그렇다면 “움직이지 않아도 되는 어린이들”이 가장 길게 남는 경우를 찾으면,
전체에서 그 길이를 뺀 값이 이동해야 하는 최소 횟수가 됩니다.

---

2. 알고리즘 아이디어

1. 각 어린이 번호의 현재 위치를 myMap에 저장합니다.
   예를 들어, 번호 3이 2번째 위치에 있다면 myMap[3] = 2 입니다.
2. 1부터 N까지 순회하면서,
   • myMap[i] < myMap[i+1] 이라면,
     번호 i가 i+1보다 앞에 서 있으므로 올바른 순서입니다.
     → 연속 구간 길이를 cnt++
   • 그렇지 않다면,
     순서가 끊기므로 cnt = 1로 초기화합니다.
3. 연속 구간 중 가장 긴 길이를 best로 기록합니다.
4. 전체 인원 N에서 best를 뺀 값이 최소 이동 횟수입니다.

---

5. 시간 복잡도

• 입력 크기: 최대 1,000,000
• map 접근: O(log N)
• 전체: O(N log N)

번호 범위가 1부터 N까지라면 vector<int>로 바꿔서 O(N)에 구현할 수도 있습니다.

---

6. 정리

• 핵심 아이디어: 움직이지 않아도 되는 연속된 오름차순 구간 찾기
• 결과 계산: N - 최장 연속 오름차순 구간 길이
• 일반적인 LIS(최장 증가 부분 수열) 문제와 달리,
  연속된 값(+1씩 증가) 만 인정된다는 점이 포인트입니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> arr(N);
    map<int, int> myMap; 

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        myMap[arr[i]] = i;
    }

    int cnt = 1;
    int best = 1;

    for (int i = 1; i < N; i++) {          
        if (myMap[i] < myMap[i + 1]) {   
            cnt++;
            best = max(best, cnt);
        }
        else {
            cnt = 1;
        }
    }

    cout << N - best << "\n";
    return 0;
}