BOJ : https://www.acmicpc.net/problem/7570

github : https://github.com/junho0956/Algorithm/blob/master/7570/7570/%EC%86%8C%EC%8A%A4.cpp

 

무작위로 위치시킬 수 있는 경우는 가장 긴 증가수열을 뺀 값으로 해결할 수 있지만

맨 앞이나 뒤로 위치시켜야 하는 경우는 lis로 해결할 수 없습니다.

1씩 연속적으로 증가하는 가장 긴 증가수열을 제외한 값들을 이동시켜야 합니다.

 

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
// 1씩 증가하는 lis 를 구한다.
// 5 2 4 1 3
/*
0 0 0 0 0
0 0 0 0 1
0 1 0 0 1
0 1 0 1 1
1 1 0 1 1
1 1 2 1 1
*/
 
#include <iostream>
using namespace std;
 
int dp[1000001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int n; cin >> n;
        dp[n] = dp[n - 1] + 1;
        ans = ans < dp[n] ? dp[n] : ans;
    }
    cout << N - ans;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 3745번 오름세  (0) 2020.02.11
BOJ 11568번 민균이의 계략  (0) 2020.02.11
BOJ 2631번 줄 세우기  (0) 2020.02.10
BOJ 2605번 줄 세우기  (0) 2020.02.10
BOJ 1681번 줄 세우기  (0) 2020.02.10

BOJ : https://www.acmicpc.net/problem/2631

github : https://github.com/junho0956/Algorithm/blob/master/2631/2631/%EC%86%8C%EC%8A%A4.cpp

 

어떻게 푸는건지 감을 못잡았는데

문제 예시에서 움직이는 4, 7, 1, 2 를 제외한 3, 5, 6은 이미 정렬이 되어있는 상태였고

3, 5, 6 자체가 증가하는 부분수열이니

문제에서 가장 긴 증가하는 부분수열을 찾는다는 생각으로 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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[201];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp.push_back(arr[0]);
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (dp[lis] < arr[i]) {
            dp.push_back(arr[i]);
            lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lo] = arr[i];
        }
    }
 
    cout << N - (lis + 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11568번 민균이의 계략  (0) 2020.02.11
BOJ 7570번 줄 세우기  (0) 2020.02.10
BOJ 2605번 줄 세우기  (0) 2020.02.10
BOJ 1681번 줄 세우기  (0) 2020.02.10
BOJ 4781번 사탕가게  (0) 2020.02.10

BOJ : https://www.acmicpc.net/problem/2605

github : https://github.com/junho0956/Algorithm/blob/master/2605/2605/%EC%86%8C%EC%8A%A4.cpp

 

다음은 직접 list 를 구현하여 해결한 코드입니다.

 

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
#include <iostream>
using namespace std;
 
struct node {
    int num;
    node* first;
    node* back;
    bool r, b;
    
    node() {
        this->first = NULL, this->back = NULL;
        this->r = this->b = false;
    }
 
    void insert(node * np, int cnt, int ans) {
        node* p = np;
        if (cnt == 0) {
            node* newp = new node();
            p->first->back = newp;
            newp->first = p->first;
            newp->back = p;
            p->first = newp;
            newp->num = ans;
        }
        else {
            p->insert(p->first, cnt - 1, ans);
        }
    }
 
    void print_node(node* p) {
        if (p->b) return;
        cout << p->num << " ";
        p->print_node(p->back);
    }
};
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    node* root = new node();
    node* broot = new node();
    root->back = broot;
    broot->first = root;
    root->r = broot->b = true;
 
    int N; cin >> N;
 
    for (int i = 1; i <= N; i++) {
        int cnt; cin >> cnt;
        broot->insert(broot, cnt, i);
    }
 
    root->print_node(root->back);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

다음은 list STL 을 사용하여 해결한 코드입니다.

 

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
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
 
using namespace std;
 
int main() {
 
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n; cin >> n;
 
    list<int> arr;
    list<int>::iterator iter;
    for (int i = 1; i <= n; i++) {
        int cand; cin >> cand;
 
        for (iter = arr.begin(); iter != arr.end(); iter++) {
            if (cand == 0) {
                break;
            }
            cand--;
        }
 
        arr.insert(iter, i);
    }
 
 
    for (auto i = arr.rbegin(); i != arr.rend(); i++) {
        cout << *i << " ";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 7570번 줄 세우기  (0) 2020.02.10
BOJ 2631번 줄 세우기  (0) 2020.02.10
BOJ 1681번 줄 세우기  (0) 2020.02.10
BOJ 4781번 사탕가게  (0) 2020.02.10
BOJ 9507번 Generations of Tribbles  (0) 2020.02.10

BOJ : https://www.acmicpc.net/problem/1681

github : https://github.com/junho0956/Algorithm/blob/master/1681/1681/%EC%86%8C%EC%8A%A4.cpp

 

마구잡이식으로 각 숫자마다 %10을 통해서 라벨 유무를 확인하는 식으로 구현하였는데

처음에는 TLE가 될 줄 알았지만 다행히? 성공하였습니다.

 

 

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
#include <iostream>
using namespace std;
typedef long long ll;
ll arr[1000001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    int val = 1;
    for (int i = 1; i <= n; i++) {
        int num = val;
        bool check = true;
        while (num) {
            if (num % 10 == m) { check = false; break; }
            num /= 10;
        }
        if (check) arr[i] = val++;
        else i--, val++;
    }
 
    cout << arr[n];
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2631번 줄 세우기  (0) 2020.02.10
BOJ 2605번 줄 세우기  (0) 2020.02.10
BOJ 4781번 사탕가게  (0) 2020.02.10
BOJ 9507번 Generations of Tribbles  (0) 2020.02.10
BOJ 1914번 하노이 탑  (0) 2020.02.10

+ Recent posts

티스토리툴바