A번 문제: 최소 변경 횟수
이 문제는 비내림차순 수열로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 주어진 수열이 비내림차순이 아니므로, 가장 많은 원소를 그대로 유지할 수 있는 경우를 찾아야 합니다.
비내림차순 수열에서 가장 많이 유지할 수 있는 원소들은 동일한 값의 연속된 부분입니다. 따라서 가장 긴 동일한 값의 연속 부분의 길이를 찾으면 됩니다.
다음은 문제의 해결 코드입니다:
#include
using namespace std;
const int MAX_SIZE = 55;
int sequence[MAX_SIZE];
int n;
int solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> sequence[i];
}
int max_length = 0;
int current_length = 0;
for (int i = 1; i <= n; i++) {
if (sequence[i] != sequence[i-1]) {
max_length = max(max_length, current_length);
current_length = 1;
} else {
current_length++;
}
}
max_length = max(max_length, current_length);
return n - max_length;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
cout << solve() << '\n';
}
return 0;
} B번 문제: 위치 교환 가능성
이 문제는 각 원소가 자신의 목표 위치로 이동할 수 있는지 확인하는 문제입니다. 주어진 조건에 따라 원소는 인접한 값과만 교환할 수 있습니다.
각 원소가 목표 위치로 이동하기 위해 필요한 교환 횟수를 분석합니다. 각 원소는 최대 한 번만 교환할 수 있으며, 교환 후에는 해당 원소가 목표 위치에 있어야 합니다.
다음은 문제의 해결 코드입니다:
#include
using namespace std;
const int MAX_SIZE = 200005;
int permutation[MAX_SIZE];
int n;
bool isPossible() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> permutation[i];
}
for (int i = 1; i <= n; i++) {
// 현재 위치가 목표 위치보다 작은 경우
if (permutation[i] < i) {
// 인접한 위치로만 교환 가능한지 확인
if (!(i - permutation[i] == 1 && permutation[permutation[i]] == permutation[i] + 1)) {
return false;
}
}
// 현재 위치가 목표 위치보다 큰 경우
else if (permutation[i] > i) {
// 인접한 위치로만 교환 가능한지 확인
if (!(permutation[i] - i == 1 && permutation[permutation[i]] == permutation[i] - 1)) {
return false;
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
cout << (isPossible() ? "Yes" : "No") << '\n';
}
return 0;
} C번 문제: 특수 수열 구성
이 문제는 주어진 조건을 만족하는 수열을 구성하는 문제입니다. 조건은 동일한 값의 원소들 사이의 거리가 완전제곱수여야 합니다.
먼저 짝수 길이의 경우는 간단하게 해결할 수 있습니다. 1,1,2,2,3,3,... 과 같이 연속된 두 개씩 배치하면 됩니다.
홀수 길이의 경우에는 복잡합니다. 동일한 값의 원소들 사이의 거리가 완전제곱수가 되도록 구성해야 합니다. 3,4,5의 피타고라스 삼각형을 이용해 특별한 구성을 만들 수 있습니다.
다음은 문제의 해결 코드입니다:
#include
using namespace std;
const int MAX_SIZE = 200005;
int result[MAX_SIZE];
int n;
void constructSequence() {
cin >> n;
if (n % 2 == 0) {
// 짝수 길이의 경우 간단한 패턴으로 구성
int current = 1;
for (int i = 1; i <= n; i += 2) {
result[i] = result[i+1] = current;
current++;
}
} else {
// 홀수 길이의 경우 특별한 구성이 필요
if (n >= 27) {
// 3,4,5 피타고라스 삼각형을 이용한 특별한 위치 설정
result[1] = result[10] = result[26] = 1;
int current = 1;
// 첫 부분 구성
for (int i = 2; i <= 8; i += 2) {
result[i] = result[i+1] = ++current;
}
// 중간 부분 구성
for (int i = 11; i <= 21; i += 2) {
result[i] = result[i+1] = ++current;
}
// 마지막 부분 구성
result[23] = result[27] = ++current;
result[24] = result[25] = ++current;
// 나머지 부분 구성
for (int i = 28; i <= n; i += 2) {
result[i] = result[i+1] = ++current;
}
} else {
// 너무 작은 길이의 경우 해결 불가
cout << -1 << '\n';
return;
}
}
// 결과 출력
for (int i = 1; i <= n; i++) {
cout << result[i] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
constructSequence();
}
return 0;
} D번 문제: 구간 병합
이 문제는 주어진 조건에 따라 구간을 병합하는 문제입니다. 역순쌍(逆序對)을 이용하여 점프 가능한 위치를 결정하고, 이를 이용해 구간을 병합합니다.
우선 배열을 한 번 순회하며 현재까지의 최댓값과 그 위치를 기록합니다. 새로운 원소가 현재 최댓값보다 작으면 이 위치와 최댓값 위치를 병합합니다.
이후 배열을 거꾸로 순회하며 병합 가능한 구간을 찾습니다. 인접한 구간들 사이에서 최솟값과 최댓값의 관계를 확인하여 병합 가능 여부를 결정합니다.
다음은 문제의 해결 코드입니다:
#include
using namespace std;
const int MAX_SIZE = 500005;
int elements[MAX_SIZE];
int parent[MAX_SIZE];
int min_val[MAX_SIZE];
int max_val[MAX_SIZE];
int n;
int findParent(int x) {
if (parent[x] == x) return x;
return parent[x] = findParent(parent[x]);
}
void mergeSets(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
min_val[x] = min(min_val[x], min_val[y]);
max_val[x] = max(max_val[x], max_val[y]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> elements[i];
parent[i] = i;
min_val[i] = max_val[i] = elements[i];
}
int current_max = elements[1];
int max_index = 1;
// 앞에서 뒤로 순회하며 초기 구간 형성
for (int i = 2; i <= n; i++) {
if (elements[i] < current_max) {
mergeSets(max_index, i);
} else {
current_max = elements[i];
max_index = i;
}
}
// 뒤에서 앞으로 순회하며 병합 가능한 구간 확인
for (int i = n-1; i >= 1; i--) {
int set1 = findParent(i);
int set2 = findParent(i+1);
if (set1 != set2 && min_val[set2] < max_val[set1]) {
mergeSets(i, i+1);
}
}
// 각 구간의 최댓값 출력
for (int i = 1; i <= n; i++) {
cout << max_val[findParent(i)] << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}