반응형

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

 

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

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

 

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

 

4. sum 배열에 존재한다면 upper_bound를 활용하여 같은 수가 있다면 그 개수만큼 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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int arr[4][4000];
vector<int> sum;
int n;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> arr[j][i];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum.push_back(arr[0][i] + arr[1][j]);
        }
    }
 
    sort(sum.begin(), sum.end());
 
    ll ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp = arr[2][i] + arr[3][j];
 
            auto it = lower_bound(sum.begin(), sum.end(), -temp);
 
            if (*it == -temp) {
                ans += upper_bound(sum.begin(), sum.end(), -temp) - it;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 2295번 - 세 수의 합 (C++)  (0) 2023.07.14
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
반응형

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/16287

 

16287번: Parcel

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

모든 경우의 수를 체크하기에는 $O(N^{4})$이라는 너무 많은 시간이 걸리므로 이를 반으로 쪼개 $O(N^{2} + N^{2})$의 시간 복잡도로 문제를 풀었습니다.

 

두 물건의 무게를 인덱스 값으로 하고, dp배열에는 각 물건의 인덱스 값을 저장합니다.

 

dp[ weight ] = i

dp2[ weight ] = j

 

이때 각 물품의 무게는 모두 다르므로 특정한 weight를 만족하는 쌍은 무슨 일이 있어도 겹치지 않으므로 한 쌍만 저장해주면 됩니다.

 

그리고 다시 한번 $O(N^{2})$의 시간 복잡도로 모든 쌍을 검사하면서 인덱스가 겹치지 않는 쌍이 있다면 YES를 출력해주고, 그렇지 않다면 NO를 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
 
using namespace std;
 
int w, n;
int arr[5000];
int dp[400001];
int dp2[400001];
 
 
int main()
{
    scanf("%d %d", &w, &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = arr[i] + arr[j];    //먼저 2개씩 더한 값들을 dp에 idx와 함께 저장
            if (dp[weight] == 0) {
                dp[weight] = i;
                dp2[weight] = j;
            }
        }
    }
 
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = w - arr[i] - arr[j];
            if (weight > 400000 || weight < 0) continue;    //불가능한 경우
            if (dp[weight] == i || dp2[weight] == j || dp[weight] == j || dp2[weight] == i || dp[weight] == 0) continue;    //idx가 겹치는 경우
            printf("YES");    //위의 조건이 아니라면 YES 출력
            return 0;
        }
    }
 
    printf("NO");    //불가능하다면 NO 출력
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 11438번 - LCA 2 (C++)  (0) 2022.08.04
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
반응형

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

티스토리툴바