반응형

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

+ Recent posts

티스토리툴바