반응형

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
반응형

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

 

1208번: 부분수열의 합 2

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

N개의 정수의 모든 부분 수열을 구하기 위해서는 O(2^N)의 시간이 걸립니다.

 

이 문제에서 N은 40개이므로 총 2^40의 시간이 필요한데 1초는 매우 부족한 시간이므로 N을 반으로 나누어 2^20 * 2 = 2^21의 시간이 걸리도록 했습니다.

 

먼저 왼쪽의 부분 수열의 합을 모두 구해 map에 넣고, 오른쪽 부분 수열의 합을 S의 값과 비교하여 cnt에 map[S-sum]을 더해주었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int N, S;
int arr[41];
unordered_map<int, int> map;
int sum = 0;
long long cnt = 0;
 
void leftDFS(int level)                //왼쪽 반의 모든 조합을 map에 저장
{
    if (level == N / 2) {
        map[sum]++;
        return;
    }
 
    sum += arr[level];
    leftDFS(level + 1);
    sum -= arr[level];
    leftDFS(level + 1);
}
 
void rightDFS(int level)            //오른쪽 반의 모든 조합을 S와 비교해
{                                    //cnt에 더해줌
    if (level == N) {
        cnt += map[S - sum];
        return;
    }
 
    sum += arr[level];
    rightDFS(level + 1);
    sum -= arr[level];
    rightDFS(level + 1);
}
 
int main()
{
    cin >> N >> S;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    leftDFS(0);
    rightDFS(N / 2);
 
    if (S == 0) cnt--;                //S가 0인 경우 공집합이 2번 들어가므로 1을 빼준다.
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22

+ Recent posts

티스토리툴바