반응형

https://www.acmicpc.net/problem/14459

 

14459번: 소가 길을 건너간 이유 11

우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. a 배열을 만들어 왼쪽 소들의 종 번호의 인덱스를 저장하고, b 배열을 만들어 오른쪽 소들의 종 번호의 인덱스를 저장합니다.

 

2. 이중 for문을 이용하여 절댓값의 차이가 4 이하인 쌍을 vector<pair<int,int>>에 저장합니다.

 

3. 이 때 first의 값을 기준으로 오름차순, second의 값을 기준으로 내림차순으로 정렬합니다.

 

4. lower_bound를 이용하여 LIS를 만들어 주고, 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int a[100001];
int b[100001];
vector<pair<int, int>> arr;
 
bool cmp(pair<int, int> left, pair<int, int> right) 
{
    if (left.first == right.first) return left.second > right.second;
    return left.first < right.first;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        a[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        b[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = max(1, i - 4); j <= min(N, i + 4); j++) {
            arr.push_back({ a[i], b[j] });
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    vector<int>lis;
 
    for (auto& next : arr) {
        if (lis.empty()) {
            lis.push_back(next.second);
        }
        else {
            auto it = lower_bound(lis.begin(), lis.end(), next.second);
            if (it == lis.end()) {
                lis.push_back(next.second);
            }
            else {
                *it = next.second;
            }
        }
    }
 
    cout << lis.size();
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
반응형

https://www.acmicpc.net/problem/3066

 

3066번: 브리징 시그널

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. arr 배열을 만들어서 입력받은 포트 번호를 저장합니다.

 

2. lower_bound를 이용하여 LIS의 길이를 구하고, LIS.size()를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int arr[40000];
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int N;
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++) {
            scanf("%d", &arr[i]);
        }
 
        vector<int> LIS;
        LIS.push_back(arr[0]);
 
        for (int i = 1; i < N; i++) {
            if (LIS[LIS.size() - 1] < arr[i]) {
                LIS.push_back(arr[i]);
            }
            else {
                auto it = lower_bound(LIS.begin(), LIS.end(), arr[i]);
                *it = arr[i];
            }
        }
 
        printf("%d\n", (int)LIS.size());
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14284번 - 간선 이어가기 2 (C++)  (0) 2023.03.03
[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 2660번 - 회장뽑기 (C++)  (0) 2023.02.28
[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
반응형

https://www.acmicpc.net/problem/3745

 

3745번: 오름세

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS.size()를 출력합니다.

 

3. n을 입력받는 scanf의 반환값이 1이 아닐 때 break로 나와줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    while (1) {
        int n;
        vector<int> LIS;
        if (scanf("%d", &n) != 1) {
            break;
        }
        
        int num;
        scanf("%d", &num);
 
        LIS.push_back(num);
 
        for (int i = 1; i < n; i++) {
            scanf("%d", &num);
            if (LIS[LIS.size() - 1] < num) {
                LIS.push_back(num);
            }
            else {
                auto idx = lower_bound(LIS.begin(), LIS.end(), num);
                *idx = num;
            }
        }
 
        printf("%d\n", LIS.size());
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
반응형

https://www.acmicpc.net/problem/12738

 

12738번: 가장 긴 증가하는 부분 수열 3

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS.size()를 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<algorithm>
 
using namespace std;
 
int N;
vector<int> LIS;
 
int main()
{
    scanf("%d", &N);
 
    int n;
 
    scanf("%d", &n);
 
    LIS.push_back(n);
 
    for (int i = 1; i < N; i++) {
        scanf("%d", &n);
        if (LIS[LIS.size() - 1] < n) {
            LIS.push_back(n);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), n);
            *idx = n;
        }
    }
 
    printf("%d", LIS.size());
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1922번 - 네트워크 연결 (C++)  (0) 2022.12.23
[ 백준 ] 14395번 - 4연산 (C++)  (0) 2022.12.22
[ 백준 ] 1818번 - 책정리 (C++)  (0) 2022.12.20
[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19
[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
반응형

https://www.acmicpc.net/problem/1818

 

1818번: 책정리

동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고  현재 뒤죽박죽 되어있는 순서를 왼쪽부터

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. N - LIS.size()를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
vector<int> LIS;
 
int main()
{
    scanf("%d", &N);
 
    int num;
 
    scanf("%d", &num);
 
    LIS.push_back(num);
 
    for (int i = 1; i < N; i++) {
        scanf("%d", &num);
 
        if (LIS[LIS.size() - 1] < num) {
            LIS.push_back(num);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), num);
            *idx = num;
        }
    }
 
    printf("%d", N - LIS.size());
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14395번 - 4연산 (C++)  (0) 2022.12.22
[ 백준 ] 12738번 - 가장 긴 증가하는 부분 수열 3 (C++)  (0) 2022.12.21
[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19
[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
반응형

https://www.acmicpc.net/problem/12014

 

12014번: 주식

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. LIS의 길이가 K보다 크거나 같다면 1, 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        int N, K;
        int num;
        vector<int> LIS;
 
        scanf("%d %d", &N, &K);
 
        scanf("%d", &num);
 
        LIS.push_back(num);
 
        for (int i = 1; i < N; i++) {
            scanf("%d", &num);
            if (LIS[LIS.size() - 1] < num) {
                LIS.push_back(num);
            }
            else {
                auto idx = lower_bound(LIS.begin(), LIS.end(), num);
                *idx = num;
            }
        }
 
        printf("Case #%d\n", t);
 
        if (LIS.size() >= K) {
            printf("1\n");
        }
        else {
            printf("0\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 22255번 - 호석사우루스 (C++)  (0) 2022.12.19
[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
반응형

https://www.acmicpc.net/problem/1365

 

1365번: 꼬인 전깃줄

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. lower_bound를 활용하여 LIS의 길이를 구합니다.

 

2. N - LIS.size()를 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[100000];
vector<int> LIS;
 
//int lower_bound(vector<int> vect, int num)
//{
//    int lo = -1;
//    int hi = vect.size() - 1;
//
//    while (lo + 1 < hi) {
//        int mid = (lo + hi) / 2;
//        if (vect[mid] < num) {
//            lo = mid;
//        }
//        else {
//            hi = mid;
//        }
//    }
//
//    return hi;
//}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    LIS.push_back(arr[0]);
 
    for (int i = 1; i < N; i++) {
        if (LIS[LIS.size() - 1] < arr[i]) {
            LIS.push_back(arr[i]);
        }
        else {
            auto idx = lower_bound(LIS.begin(), LIS.end(), arr[i]);
            *idx = arr[i];
        }
    }
 
    printf("%d", N - LIS.size());
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 6593번 - 상범 빌딩 (C++)  (0) 2022.12.18
[ 백준 ] 12014번 - 주식 (C++)  (0) 2022.12.17
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 2812번 - 크게 만들기 (C++)  (0) 2022.12.14
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
반응형

https://www.acmicpc.net/problem/2550

 

2550번: 전구

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

글을 읽기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. 스위치를 순서대로 저장할 배열과 스위치의 위치를 저장할 배열을 각각 만들어 값을 저장합니다.

 

2. 전구의 위치를 저장할 배열을 만들어 값을 저장합니다.

 

3. lower_bound를 이용해 LIS를 만들고, 각각의 스위치가 LIS에서 몇 번째 idx에 있는지 idx 배열을 만들어 값을 저장합니다.

 

4. idx 배열의 끝에서부터 for문을 돌면서 LIS에 들어갈 스위치를 ans 배열에 저장합니다.

 

5. ans 배열을 정렬합니다.

 

6. LIS의 size를 출력하고, ans에 저장된 값을 하나씩 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
int sw[10001];        //sw[i] = 스위치 번호
int pos[10001];        //pos[스위치 번호] = i
int bulb[10001];    //전구의 순서
int idx[10001];        //LIS에서 몇번 째 위치해 있는지 저장할 배열
vector<int> LIS;
vector<int> ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int idx;
        scanf("%d", &idx);
        sw[i] = idx;
        pos[idx] = i;
    }
 
    for (int i = 0; i < N; i++) {
        int idx;
        scanf("%d", &idx);
        bulb[pos[idx]] = i;
    }
 
    LIS.push_back(bulb[0]);
    idx[0] = 1;
 
    for (int i = 1; i < N; i++) {        //lower_bound
        if (bulb[i] > LIS[LIS.size() - 1]) {
            LIS.push_back(bulb[i]);
            idx[i] = LIS.size();
        }
        else {
            auto it = lower_bound(LIS.begin(), LIS.end(), bulb[i]);
            *it = bulb[i];
            idx[i] = it - LIS.begin() + 1;    //현재 스위치의 LIS에서의 위치
        }
    }
 
    int cur = LIS.size();
 
    for (int i = N - 1; i >= 0; i--) {
        if (idx[i] == cur) {
            ans.push_back(sw[i]);
            cur--;
        }
    }
 
    sort(ans.begin(), ans.end());
 
    printf("%d\n", LIS.size());
 
    for (int i = 0; i < LIS.size(); i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
반응형

https://www.acmicpc.net/problem/2568

 

2568번: 전깃줄 - 2

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/35?category=1064612 

 

[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00..

rudalsd.tistory.com

 

위의 문제와 답을 구하는 과정은 똑같지만 결과를 출력하는 방법이 조금 달랐습니다. 이번 문제는 LIS에 포함되지 않는 수의 개수와 포함되지 않는 수들을 오름차순으로 출력하는 문제였습니다.

 

출력 전까지는 위의 문제와 똑같은 방법으로 문제를 풀어나가지만 마지막에 원하는 index가 아닐 때 ans에 숫자를 push 해줍니다.

 

[ 소스 코드 ]

 

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
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
int N;
map<int, int> A;        //전깃줄이 연결된 번호
map<int, int> idx;        //LIS에서의 index를 저장할 map
vector<int> LIS;
vector<int> ans;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        A[a] = b;
    }
 
    for (auto it = A.begin(); it != A.end(); it++) {
        if (LIS.size() == 0) {
            LIS.push_back(it->second);
            idx[it->first] = 1;
        }
        else {
            if (*LIS.rbegin() < it->second) {
                LIS.push_back(it->second);
                idx[it->first] = LIS.size();
            }
            else {
                int a = lower_bound(LIS.begin(), LIS.end(), it->second) - LIS.begin();
                LIS[a] = it->second;
                idx[it->first] = a + 1;
            }
        }
    }
 
    int cnt = LIS.size();
 
    for (auto it = idx.rbegin(); it != idx.rend(); it++) {
        if (it->second == cnt) {        //뒤에서부터 LIS index를 하나씩 줄여가면서
            cnt--;
        }
        else {                    //원했던 index와 다르다면 ans에 push
            ans.push_back(it->first);
        }
    }
 
    printf("%d\n", ans.size());        //없애야하는 전깃줄의 개수 출력
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d\n", ans[i]);        //뒤에서부터 ans에 저장된 전깃줄 출력
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
반응형

https://www.acmicpc.net/problem/14003

 

14003번: 가장 긴 증가하는 부분 수열 5

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

lower_bound를 잘 활용하고 각 수의 index를 잘 저장해주면 쉽게 풀 수 있는 문제입니다.

 

먼저 각 수의 index를 저장할 index배열을 만듭니다. 그리고 각 수가 LIS의 몇 번째 인덱스에 있는지 계속 체크해주면서 index 배열에 저장해줍니다.

 

10 20 10 30 20 50

 

위의 수열을 예로 들면 

 

 

그리고 나서 index배열의 끝에서부터 값이 큰 수부터 차례로 ans 배열에 저장한 후 ans 배열을 출력해주면 됩니다.

 

 

[ 소스 코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
vector<int> lis;
vector<int> ans;
int arr[1000001];        //전체 배열
int index[1000001];        //lis 좌표를 저장하기 위한 배열
 
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        if (i == 0) {
            lis.push_back(arr[i]);
            index[i] = lis.size();        //lis의 몇번 째에 있는지 저장
        }
        else {
            if (*lis.rbegin() < arr[i]) {
                lis.push_back( arr[i] );
                index[i] = lis.size();    //lis의 몇번 째에 있는지 저장
            }
            else {
                auto idx = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
                lis[idx] = arr[i];        
                index[i] = idx + 1;        //lis의 몇번 째에 있는지 저장
            }
        }
    }
 
    int cnt = lis.size();
 
    for (int i = N - 1; i >= 0; i--) {    //반대부터 index를 1씩 줄여가며 순서대로 저장
        if (index[i] == cnt) {
            ans.push_back(arr[i]);
            cnt--;
        }
 
        if (cnt == 0) break;
    }
 
    cout << lis.size() << endl;
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18

+ Recent posts

티스토리툴바