티스토리 뷰
대회 때 1시간동안 못풀고 끝난 문제다~~!
그리디 처럼 생각했는데 결국 떠오르지가 않는다
그리디와 수학 연습을 해야한다는걸 코포 할 때마다 느끼게된다
먼저 이 문제를 어떻게 접근해야할까
내가 가장 큰 LIS를 찾는다고 생각하면 그건 <의 수에 의존하게된다
<이 나타날때마다 작은수를 차례대로 넣어주면 <의 수 +1만큼이 최대가 될 것이다
작은경우도 비슷하게 생각하면 연속적인 <의 수 1이 될것이다!!
(맞나 기억이 잘 안난다..!)
그래서 이제 큰 경우를 찾아보자
큰 LIS를 찾을 때는 <을 찾을때마다 앞에 작은수를 채우면 된다
연속적인 <에서 맨 뒤는 빈 자리로 남겨둔다
왜냐면 다음 >을 채울 때 채워야하기 때문에!
<을 다 채운 다음에는 큰 수부터 >을 채우면 된다
작은경우는 반대로 하면 된다
조금 더럽게풀어서 소스가 좀 더럽다...!
근데 이런 문제를 풀 때는 경우를 정리하면서
언제가 확실히 최적이 되는지 좀 손으로 써가며 정리를 해야겠다
소스코드
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int maxarr[MAXN], minarr[MAXN];
string s;
int n;
int main() {
int t; scanf(" %d", &t);
while (t--) {
scanf(" %d", &n);
cin >> s;
memset(maxarr, 0, sizeof(maxarr));
memset(minarr, 0, sizeof(minarr));
int num = 1;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '<') {
int j = i;
while (s[j] == '<' && i <= n - 1)j++;
for (int k = i; k < j; k++) maxarr[k] = num++;
i = j - 1;
}
}
num = n;
for (int i = 0; i < n; i++) if (!maxarr[i]) maxarr[i] = num--;
num = n;
for (int i = 0; i < n - 1; i++) {
if (s[i] == '>') {
int j = i;
while (s[j] == '>' && j < n - 1) j++;
for (int k = i; k < j; k++) minarr[k] = num--;
if (j == n - 1) minarr[j] = 1;
i = j - 1;
}
}
for (int i = 0; i < n - 1; i++) {
if (!minarr[i]) {
int j = i;
while (!minarr[j] && j <= n - 1) j++;
for (int k = i; k < j; k++) minarr[k] = num--;
reverse(minarr + i, minarr + j);
}
}
for (int i = 0; i < n; i++) printf("%d ", minarr[i]); puts("");
for (int i = 0; i < n; i++) printf("%d ", maxarr[i]); puts("");
}
}
|
'알고리즘 > Codeforces' 카테고리의 다른 글
R621(Div.1+Div.2) B. Cow and Friend (0) | 2020.02.19 |
---|---|
R621(Div.1+Div.2) A. Cow and Haybales (0) | 2020.02.19 |
Edu82(Div.2) D. Fill The Bag (0) | 2020.02.16 |
R620(Div.2) C.Air Conditioner (0) | 2020.02.16 |
R620(Div.2) B.Longest Palindrome (0) | 2020.02.16 |
댓글