반응형

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

 

2295번: 세 수의 합

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수들을 입력받아 arr 배열에 저장하고, arr 배열에서 두 수를 뽑아 더한 값을 sum 배열에 저장합니다. 

 

2. arr 배열과 sum 배열을 오름차순으로 정렬합니다.

 

3. 이중 for문을 이용하여 i = N - 1부터 0까지, j는 0부터 N까지 탐색하면서 arr[ i ] - arr[ j ]가 sum 배열에 존재하는지 lower_bound를 활용하여 찾아줍니다.

 

4. sum 배열에 존재한다면 해당 수가 최댓값이므로 arr[ i ]를 출력해 줍니다.

 

[ 소스코드 ]

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 N;
int arr[1000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    vector<int> sum;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            sum.push_back(arr[i] + arr[j]);
        }
    }
 
    sort(arr, arr + N);
    sort(sum.begin(), sum.end());
 
    int ans = 0;
 
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (*lower_bound(sum.begin(), sum.end(), arr[i] - arr[j]) == arr[i]-arr[j]) {
                cout << arr[i];
                return 0;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
반응형

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

+ Recent posts

티스토리툴바