백준 1898 - 이전 수열은 어떤 수열일까
Updated:
Categories: Problem Solving
Tags: 그리디
이전 수열은 어떤 수열일까
풀이
원래 수가 x이고 새로운 수가 nx로 두고 싶다고 하자.
왼쪽부터 접근한다고 했을 때 가장 작은 수가 되려면 nx는 x보다 작으면 좋고 최소한 같아야 한다.
따라서 nx = x-1이거나 x이다. nx = x인 경우는 그냥 그대로 넣으면 되므로 상관없고 nx = x-1인 경우를 살펴보자.
1
2
원래: x ... x-1
새로운: x-1 ... ?
? 자리에 x-1은 이미 사용해서 올 수 없으므로 x-2나 x가 가능하다. 만약 ?에 x-2가 오게 된다면 원래의 x-2에는 x-3, x-2, x-1중에서 쓸 수 있는 수가 x-3만 사용 가능하므로 점점 작아진다. 이는 1이상의 차이가 나는 자리가 생길 수 밖에 없다.
따라서 ?는 x만 올 수 있다.
이를 이용해서 그리디하게 풀면 해결 가능하다.
코드
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
#include <bits/stdc++.h>
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second
using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();
void solve() {
int n; cin >> n;
vector<int> link(n+1,-1);
FOR(i,1,n) {
int x; cin >> x;
if(link[x] == -1) {
for(int nx=max(1,x-1); nx<=min(n,x+1); nx++) {
if(link[nx] != -1) continue;
link[x] = nx;
link[nx] = x;
break;
}
}
cout << link[x] << endl;
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int TC=1;
// cin >> TC;
FOR(tc, 1, TC) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Leave a comment