BOJ 32944 잘못된 LIS 알고리즘

문제 링크입니다.

문제 요약

스탈린 소트로 LIS를 찾는 알고리즘을 저격하세요. 구체적으로, 수열의 길이가 $N$, LIS의 길이가 $M$, 위의 알고리즘으로 찾은 증가 수열의 길이가 $K < M$인 수열을 제시하세요.

풀이

$N = M$인 경우 저격이 불가능합니다. LIS의 길이가 $N$인 게 이미 오름차순인 수열밖에 없는데 이러면 그리디하게 돌려도 맞는 값이 나와서 그래요.

하지만 나머지 경우는 항상 저격이 가능함을 알 수 있습니다. 방법은 다음과 같습니다.

1. 길이가 $K-1$인 증가수열 $[1,2,\cdots,K-1]$을 생각합시다.
2. 그 뒤에 $N$을 추가합니다. 저격할 알고리즘에서 이 뒤의 원소는 싹 다 무시되므로 길이 $K$의 증가 수열이 얻어집니다.
3. 이제 $K$부터 $M-1$까지의 원소를 나열해 LIS의 길이를 $M-1$로 만들어 줍니다.
4. 그 뒤의 어느 원소를 골라도 그 원소가 LIS의 끝이도록, $N-1$부터 $M$까지의 원소를 내림차순으로 나열합니다.

이러한 방법으로 총 시간 복잡도 ${\cal O}(N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m, k; cin >> n >> m >> k;
	if(m == n) return !(cout << -1);
	for(int i = 1; i < k; i++) cout << i << ' ';
	cout << n << ' ';
	for(int i = k; i < m; i++) cout << i << ' ';
	for(int i = n-1; i >= m; i--) cout << i << ' ';
}