티스토리 뷰

 

대회 때 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, 0sizeof(maxarr));
        memset(minarr, 0sizeof(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
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/12   »
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
글 보관함