문제는 이러하다
이 문제는 N개의 바구니가 일렬로 놓여 있을 때, M번의 연산을 통해 바구니의 순서를 바꾸는 문제입니다. 각 연산은 L번 바구니부터 R번 바구니까지의 바구니 순서를 뒤집습니다. 예를 들어, 1 2 3 4 5 순서로 놓인 바구니에서 2 4 구간을 뒤집으면 1 4 3 2 5가 됩니다.
이 문제를 해결하기 위해서는 주어진 M번의 연산을 순서대로 수행하면서 바구니의 순서를 바꾸면 됩니다. 구간을 뒤집는 연산을 수행할 때는, 해당 구간의 시작 인덱스와 끝 인덱스를 이용해 뒤집을 구간을 구한 후 해당 구간을 뒤집는 방식으로 구현할 수 있습니다.
예를 들어, 배열 a가 있다고 가정하고, 2부터 4까지의 구간을 뒤집는 경우 a[2:5] = a[2:5][::-1]과 같이 구간을 뒤집을 수 있습니다. 이러한 방법으로 구현하면 연산 시간은 O(NM)이 됩니다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = i+1;
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
for (int j = 0; j < (r-l+1)/2; j++) {
swap(v[l+j-1], v[r-j-1]);
}
}
for (int i = 0; i < n; i++) {
cout << v[i] << " ";
}
cout << endl;
return 0;
}
해답
이 코드에서는 먼저 n과 m을 입력 받은 후, 벡터 v를 선언하고 1부터 n까지의 값을 순서대로 넣어줍니다. 그 다음, m번의 연산을 수행하는데, 구간을 뒤집을 때는 해당 구간의 시작 인덱스 l과 끝 인덱스 r을 입력 받고, l부터 r까지의 범위를 뒤집는 방식으로 구현합니다.
구간을 뒤집을 때는 뒤집는 범위의 길이를 나누기 2한 값만큼 반복문을 수행하며, swap 함수를 이용해 뒤집습니다. 이후에는 바구니의 순서를 출력하면 됩니다.
다른 풀이
vector를 사용하지 않고 푸는 방법입니다
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int v[n+1];
for (int i = 1; i <= n; i++) {
v[i] = i;
}
while (m--) {
int l, r;
cin >> l >> r;
while (l < r) {
swap(v[l], v[r]);
l++; r--;
}
}
for (int i = 1; i <= n; i++) {
cout << v[i] << " ";
}
cout << endl;
return 0;
}
vector 대신 배열을 이용하였기 때문에 배열의 크기를 미리 정해야 합니다. 따라서, 입력으로 받은 n에 1을 더한 크기의 배열을 선언하였습니다.
그리고, 바구니의 순서를 저장하기 위해 for문을 이용해 1부터 n까지의 값을 배열에 저장합니다.
그 다음, m번의 뒤집는 연산을 반복합니다. 각 연산에서는 뒤집을 범위인 l부터 r까지의 값을 입력 받습니다. 그리고, while문을 이용해 해당 범위를 뒤집습니다.
마지막으로, 배열의 각 요소를 출력합니다. 이를 위해 for문을 이용해 1부터 n까지의 값들을 순서대로 출력하고, 각 바구니 사이에 공백을 넣어주며, 마지막에는 줄바꿈을 해줍니다.
이렇게 배열을 이용해 문제를 해결할 수 있습니다.