재미있는 그리디 문제이다. 2년 전에 손도 못대던 문제를 풀었더니 기분이 좋다.
<풀이>
문제 내용은 1부터 N까지의 수를 한 번씩 이용해서 가장 긴 증가하는 부분 수열의 길이가 M이고, 가장 긴 감소하는 부분 수열의 길이가 K인 수열을 출력한다는 것이다.
숫자를 배열하면서 규칙을 찾아보면, 숫자를 오름차순 해둔 상태에서 M개의 그룹을 만들고, 각각의 그룹을 내림차순하면, 가장 긴 증가하는 부분 수열의 길이를 M으로 만들 수 있다. 그러면, 각각의 그룹 내에 감소하는 부분 수열이 존재하기 때문에, 그룹에 들어가는 원소의 수 중 최댓값이 K가 되게 된다.
따라서, 이 문제는 M개의 그룹에 최대 K개의 원소를 배치하는 문제로 바뀌게 된다. (무언가 굉장히 많이 본 형태!)
M개의 그룹에 최대 K개의 원소를 배치할 수 있다면, 전체 시퀀스 길이 N은 M*K를 넘을 수 없다. (비둘기집의 원리라고 생각해도 되는데 자명하다)
또한, 증가하는 부분 수열과 감소하는 부분 수열의 길이는 최소 숫자 한개만큼은 공유하기 때문에 M+K-1 <= N이 성립한다. (간단하게 1,2,3,4,5 시퀀스가 있을 때 M=5, K=1이 되는 것을 생각해보면 이 또한 자명하다)
그래서 이 두 가지 경우를 예외 컨디션으로 넣어주면 끝이다.
그냥 여기까지만 생각하고 맨 마지막 그룹에 K개의 원소를 넣어주고 나머지 그룹에 (N-K) / (m-1)개의 원소를 넣어주고 m-1번째 그룹에 나머지를 더한만큼 원소를 넣어주는 식으로 문제를 푸니 틀렸습니다가 떴다. 그러다 m=1일 때 예외 처리 안해준 것을 발견하고 수정하고, 다시 곰곰이 생각해보니, 다음의 반례가 있었다.
21 6 4
내 알고리즘대로라면 원소를 1 2 3 / 4 5 6 / 7 8 9 / 10 11 12 / 13 14 15 16 17 / 18 19 20 21 이렇게 나누게 되어서 중간에 K개보다 많은 수의 원소를 가진 그룹이 발생하게 된다.
즉, 위의 풀이 방식으로는 각 그룹에 최대 K개의 원소가 들어가는 조건이 성립하지 못하게 된다.
따라서, 풀이 방법을 다음과 같이 바꿔주었다. 맨 마지막 그룹에는 K개가 들어가게 그대로 유지하고, 나머지 그룹에는 N<=M*K라는 조건 때문에 나머지를 제외하면, 각 그룹에 들어가는 원소의 수(n_elem)는 최대 K개를 만족한다. 따라서 나머지의 수를 미리 계산해둔 후, n_elem이 K보다 작으면 n_elem + 1개의 원소를 그룹에 넣어주는 식으로 진행하였다. 그렇게 하면, 각 그룹에는 최대 K개의 원소가 들어가고, 나머지는 그룹의 개수보다는 항상 적을 수 밖에 없기 때문에 식의 조건을 성립하는 상태로 원소를 배치할 수 있다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back
int seq[501];
int N, M, K;
bool compare(int i, int j){
return j < i;
}
int main(){
cin >> N >> M >> K;
int lower_bound = M+K-1;
int upper_bound = M*K;
if (lower_bound <= N && N <= upper_bound){
// initialize : sorted
for (int i=0; i<N;i++){
seq[i] = i+1;
}
int final_group_idx = N-K;
sort(seq+final_group_idx, seq+N, compare);
int n_elem;
int remainder;
if (M == 1){
n_elem = 0;
remainder = 0;
}
else {
n_elem = (N-K) / (M-1);
remainder = (N-K) % (M-1);
}
int start = 0;
int end = 0;
for(int i=1; i<M;i++){
if (n_elem < K && remainder){
end += n_elem + 1;
remainder--;
}
else {
end += n_elem;
}
sort(seq+start, seq+end, compare);
start = end;
}
for (int i=0;i<N;i++){
cout << seq[i] << " ";
}
cout << '\n';
}
else {
cout << "-1\n";
}
return 0;
}
'컴퓨터 사이언스 > BOJ' 카테고리의 다른 글
[c++] 백준 #2206 벽 부수고 이동하기 (0) | 2022.03.02 |
---|---|
[c++] 백준 #1011 Fly me to the Alpha Centauri (0) | 2021.02.07 |
[c++] 백준 #9663 N-Queen (0) | 2021.01.24 |
[c++] 백준 #10971 외판원 순회 2 (0) | 2021.01.24 |
[c++] 백준 #1339 단어 수학 (0) | 2021.01.15 |
댓글