문제 URL : https://www.acmicpc.net/problem/2505
2505번: 두 번 뒤집기
첫줄에는 숫자판의 크기를 나타내는 정수 N (5 ≤ N ≤ 10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다.
www.acmicpc.net
문제 접근법 :
사이즈가 n인 배열에 정확히 1~n까지의 수가 있었고 그것을 정확히 두번 뒤집었을때의 입력이 들어옵니다.
그렇다면 다시 2번 뒤집어서 정렬된 결과물로 원상태로 돌려놔야하는 문제입니다.
어떻게 원래대로 돌려놓을수있을까요??
배열 왼쪽에서 첫뻔째로 순서에 맞지않는 인덱스와 그수가 몇번째에 위치해있는지를 찾아
뒤집은후 그다음 오른쪽에서 맞지않는 인덱스와 그수가 몇번재에 위치해잇는지를 찾아 뒤집어줍니다.
마찬가지로 반대로 오른쪽에서 첫번째로 순서에 맞지않는 인덱스와 그수가 몇번째에 위치해잇는지를 찾아 뒤집은후 이번엔 왼쪽도 마찬가지로 해줘야합니다.
그렇다면 여기서 딱 2가지의 경우수가 존재합니다.
1번: 왼쪽에서 찾은것을 먼저 뒤집고 오른쪽에서 뒤집을건지
2번 :오른쪽에서 찾은것을 먼저뒤집고 왼쪽에서 뒤집을건지
둘중하나는 반드시 맞는결과물이 나오기때문에 1,2번 둘다 조사하면됩니다.
저같은경우는 1번을 먼저조사하고 1번이맞을경우 출력해주고 종료시키고 아니라면
2번을 다시진행하여 출력했습니다.
그리고 예외처리를 해야하는데 하나도 뒤집을경우가 필요없는경우는 (1,1)을 뒤집든 (n,n)을 뒤집든 무조건 자기자신이 나오게 해주면 됩니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
vector<int> v;
int n;
void input() {
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
}
pii leftfind(vector<int>& a) {
for (int i = 0; i < n; i++) {
if (a[i] != i + 1) {
int idx = find(a.begin(), a.end(), i + 1) - a.begin();
return { i,idx };
}
}
return { 0,0 };
}
pii rightfind(vector<int>& a) {
for (int i = n - 1; i >= 0; i--) {
if (a[i] != i + 1) {
int idx = find(a.begin(), a.end(), i + 1) - a.begin();
return { idx,i };
}
}
return {0,0};
}
bool isfinish(vector<int>& a) {
for (int i = 0; i < n; i++)if (a[i] != i + 1)return false;
return true;
}
void solve() {
vector<pair<int, int>> res;
vector<int> v2 = v;
int l1, l2, r1, r2;
tie(l1, l2) = leftfind(v);
reverse(v.begin() + l1, v.begin() + l2 + 1);
tie(r1, r2) = rightfind(v);
reverse(v.begin() + r1, v.begin() + r2 +1);
if (isfinish(v)) {
cout << l1 + 1 << " " << l2 + 1 << "\n";
cout<< r1 + 1 << " " << r2 + 1 <<"\n";
return;
}
tie(r1, r2) = rightfind(v2);
reverse(v2.begin() + r1, v2.begin() + r2 + 1);
tie(l1, l2) = leftfind(v2);
reverse(v2.begin() + l1, v2.begin() + l2 + 1);
cout << r1 + 1 << " " << r2 + 1 << "\n";
cout << l1 + 1 << " " << l2 + 1 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한 점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1938 통나무 옮기기 (0) | 2021.08.31 |
|---|---|
| 백준 2842 집배원 한상덕 (0) | 2021.08.31 |
| 백준 17267 상남자 (0) | 2021.08.26 |
| 백준 1942 디지털 시계 (0) | 2021.08.23 |
| 백준 8595 히든 넘버 (0) | 2021.08.22 |
