LIS를 고려해서 먼저 수를 M개 뽑아 진열하고, 그 사이에 LDS를 만족할 수 있도록 나머지 수를 진열한다. 이때 M개 뽑는 것은 최대한 큰 쪽부터 뽑는다. 만약 남은 수를 어떻게 넣어도 LDS를 만족할 수 없다면 -1을 출력한다.
1부터 N까지의 수를 한번씩 이용해서, LIS의 길이가 M, LDS의 길이가 K인 수열을 출력한다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> nums;
for (int i = 1; i <= n; i++)
nums.push_back(i);
vector<int> ret;
for (int i = 0; i < m; i++) {
int x = nums.back();
nums.pop_back();
ret.push_back(x);
}
sort(ret.begin(), ret.end()); // 9 10 11 12 13
// LDS 넣기
for (int i = k - 1; i > 0; i--) {
auto iter = find(nums.begin(), nums.end(), i);
if (iter != nums.end()) {
ret.push_back(i);
nums.erase(iter);
}
} // 3 2 1
while (!nums.empty()) {
vector<int> cand;
for (int i = 0; i < k - 1; i++) {
if (!nums.empty()) {
cand.push_back(nums.front());
nums.erase(nums.begin());
}
}
reverse(cand.begin(), cand.end());
for (int i = 0; i < (int)cand.size(); i++)
ret.push_back(cand[i]);
}
// LDS 검사
vector<int> checkLDS = ret;
int u = checkLDS.size();
vector<int> length(u);
reverse(checkLDS.begin(), checkLDS.end());
length[0] = 1;
for (int i = 1; i < n; i++) {
int val = 0;
for (int j = 0; j < i; j++)
if (checkLDS[j] < checkLDS[i])
if (val < length[j]) val = length[j];
length[i] = val + 1;
}
int ans = 0;
for (int i = 0; i < n; i++)
if (ans < length[i]) ans = length[i];
if(ans == k){
for (int i = 0; i < n; i++)
cout << ret[i] << " ";
cout << endl;
}
else
cout << -1 << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int lis[40001];
int binarySearch(int left, int right, int target) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (lis[mid] < target)
left = mid + 1;
else
right = mid;
}
return right;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> nums;
for (int i = 1; i <= n; i++)
nums.push_back(i);
vector<int> ret;
for (int i = 0; i < m; i++) {
int x = nums.back();
nums.pop_back();
ret.push_back(x);
}
sort(ret.begin(), ret.end()); // 9 10 11 12 13
// LDS 넣기
for (int i = k - 1; i > 0; i--) {
auto iter = find(nums.begin(), nums.end(), i);
if (iter != nums.end()) {
ret.push_back(i);
nums.erase(iter);
}
} // 3 2 1
while (!nums.empty()) {
vector<int> cand;
for (int i = 0; i < k - 1; i++) {
if (!nums.empty()) {
cand.push_back(nums.front());
nums.erase(nums.begin());
}
}
reverse(cand.begin(), cand.end());
for (int i = 0; i < (int)cand.size(); i++)
ret.push_back(cand[i]);
}
// LDS 검사
vector<int> checkLDS = ret;
int u = checkLDS.size();
reverse(checkLDS.begin(), checkLDS.end());
lis[0] = checkLDS[0];
int a = 1, b = 0;
while (a < u) {
if (lis[b] < checkLDS[a]) {
lis[b + 1] = checkLDS[a];
b++;
}
else {
int pos = binarySearch(0, b, checkLDS[a]);
lis[pos] = checkLDS[a];
}
a++;
}
if(b + 1 == k){
for (int i = 0; i < n; i++)
cout << ret[i] << " ";
cout << endl;
}
else
cout << -1 << endl;
return 0;
}
위 두가지 방법으로 풀었다. 다른 점은 LDS를 검산하는 계산 방식이 다른거고, 둘 다 시간초과가 떴다.
해설
(1) N ≥ M + K - 1이어야 한다.
(2) N ≤ MK이다.
1 2 3 4 5 6 7 8 9 라는 수열이 주어지면, 이를 4 3 2 1 / 8 7 6 5 / 9 와 같이 수열을 정비해서, 한 그룹에서 하나씩 선택하면 증가수열, 한 그룹 내에서는 감소수열이 만들지도록 한다. 따라서 한 그룹의 크기가 감소 수열의 개수이고, 그룹의 개수가 증가 수열의 개수가 된다.
여러 그룹 중 적어도 하나는 K개의 수가 있어야 하고, 모든 그룹의 크기의 최대 수의 개수는 K개이다. 그리고 이러한 그룹들이 총 M개 있어야 한다.
N개의 숫자를 M개의 그룹으로 나누었을 때 남은 숫자의 개수를 R개라고 하자. R을 각 그룹에 1씩 나누어서 M개의 그룹 중 R개의 그룹의 숫자의 개수를 N/M + 1개라고 하고, 나머지 그룹은 N/M개의 숫자를 넣는다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, m, k; cin >> n >> m >> k;
vector<int> ret(n);
// M개의 그룹으로 나누고, 각 그룹의 크기는 최대 K개이다.
if (m + k - 1 <= n && n <= m * k) {
for (int i = 0; i < n; i++)
ret[i] = i + 1; // 1부터 N까지 넣어준다.
vector<int> group; // 그룹의 경계
group.push_back(0);
group.push_back(k); // 처음 그룹의 크기를 K로 설정
n -= k; // 남은 수의 개수
m--; // 그룹의 개수(증가 수열의 수)를 하나 제외
// 남은 n개의 숫자들을 m개의 그룹으로 나눈다.
int groupSize = (m == 0) ? 1 : n / m;
// n개의 그룹을 m으로 나누고 r개의 숫자가 남는다.
int r = (m == 0) ? 0 : n % m;
for (int i = 0; i < m; i++) {
// 그룹의 경계를 표시한다.
group.push_back(group.back() + groupSize + (r > 0 ? 1 : 0));
if (r > 0) r--;
}
for (int i = 0; i < group.size() - 1; i++)
reverse(ret.begin() + group[i], ret.begin() + group[i + 1]);
for (int i = 0; i < ret.size(); i++)
cout << ret[i] << " ";
cout << endl;
}
else
cout << -1 << endl;
return 0;
}
아이디어는 비슷했으나, 아이디어를 “그룹”이라는 형태로 정형화해서 풀지 않았다는 점이 시간초과를 냈던 것 같다. 그리고 N, M, K의 관계를 이 관점으로 분석해 m + k -1 <= n, n <= m * k인 경우에만 답을 풀 수 있다는 점을 끄집어내지 못하였다.
이동하면서 얻을 수 있는 가장 큰 숫자를 구하기
자신의 위치에서 (1) 방문하지 않았고 (2) 범위 안에 있고 (3) 가능한 전부 방문하는 것 시작하는 방향이 R이냐 D이냐에 따라 두 가지 답이 나오고 가장 큰 경로를 선택한다.