반응형

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

 

18114번: 블랙 프라이데이

첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 물건의 무게를 입력받고, 그 중 C와 값이 같은 물건이 있으면 1을 출력하고 프로그램을 종료합니다.

 

2. 1에서 무게가 C와 같은 물건이 없었다면 투포인터를 이용하여 물건 두 개를 골라 무게가 C와 같은 조합이 있으면 1을 출력하고 프로그램을 종료합니다.

 

3. 1, 2에서 무게가 C와 같은 조합이 없다면 0부터 N-3까지 for문을 이용해 돌면서 투포인터를 활용하여 물건 세 개를 골라 무게가 C와 같은 조합이 있으면 1을 출력하고 프로그램을 종료합니다.

 

4. 1, 2, 3에서 무게가 C와 같은 조합이 없다면 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, C;
int arr[5000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (arr[i] == C) {
            cout << 1;
            return 0;
        }
    }
 
    sort(arr, arr + N);
 
    int s = 0;
    int e = N - 1;
 
    while (s < e) {
        int temp = arr[s] + arr[e];
 
        if (temp > C) {
            e--;
        }
        else if (temp < C) {
            s++;
        }
        else {
            cout << 1;
            return 0;
        }
    }
 
    for (int i = 0; i < N - 2; i++) {
        s = i + 1;
        e = N - 1;
 
        while (s < e) {
            int temp = arr[i] + arr[s] + arr[e];
 
            if (temp > C) {
                e--;
            }
            else if (temp < C) {
                s++;
            }
            else {
                cout << 1;
                return 0;
            }
        }
    }
 
    cout << 0;
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 9024번 - 두 수의 합 (C++)  (0) 2023.08.11
[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05

+ Recent posts

티스토리툴바