백준 18114 블랙 프라이데이 C++

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

18114번: 블랙 프라이데이

---

문제

서강 백화점이 블랙 프라이데이를 맞아서 특별 이벤트를 진행한다. 백화점에서 제시하는 양의 정수의 무게 C에 딱 맞게 물건들을 가져오면 전부 만 원에 판매하는 이벤트이다.

선택할 수 있는 물건은 최대 3개까지이고, 같은 물건을 중복 선택하는 것은 불가능하다. 그리고 백화점에서 판매하는 물건들의 무게는 모두 다르다.

예를 들어, 백화점에서 판매하고 있는 물건 5개의 무게가 각각 1, 2, 3, 4, 5일 때, C가 5라면 {2, 3} 또는 {5}에 해당하는 물건의 조합을 만 원에 구매할 수 있다.

판매하는 물건 N개의 양의 정수의 무게가 각각 주어질 때, 만 원에 구매할 수 있는 조합이 있는지 출력하라

---

입력

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

다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진다. (1 ≤ w ≤ 108, w는 양의 정수)

---

일단 물건의 무게를 입력받아서 오름차순 정렬을 해주었다.

그 후 for문을 N까지 돌리면서(i = 0;i<N;i++)

left를 i+1번째 물건으로, right를 n-1(제일 끝에 있는 물건)으로 설정해두고,

세 물건의 합을 더해서, 그 합이 C보다 작은 경우에 left를 키우고, 합이 C보다 큰 경우에 right를 줄여주는 식으로 좁혀나갔다.

세 개의 물건의 합 뿐만 아니라 물건의 무게가 합 그자체인 경우, 2개의 물건의 합이 C인경우도 처리해줘야 해서

           /*3개의 물건의 합이 C이거나 , 1개의 물건 (i,left,right)이 C 그 자체이거나,
           2개의 물건의 합이 C인 경우 (i+left)물건, (left+right)의 물건, (i+right)의 물건 */ 을 따로 뺴주었다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
int main(void){
    /*물건은 최대 3개까지고, 같은 물건을 중복 선택해서는 안됨. 무게는 모두 다르다.
    양의 정수 C에 물건이 딱 맞는다면 만 원이라는 가격에 물건이 모두 팔림 */
    
    ll n,c;
    ll arr[5001];
 
    cin >> n >> c;
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
 
    sort(arr,arr+n); //정렬해주고, is_able -> 물건의 무게가 C인지 판별
    bool is_able = false;
    
    //i번물건부터 끝까지
    for(int i = 0;i<n;i++){
       int l = i+1; //left는 i+1의 물건 값, right는 제일 마지막의 물건 값
       int r = n-1;

       while(l<=r){
           if(l == r){ //두 물건이 중복되면 안된다.
               break;
           }
           /*3개의 물건의 합*/
           ll sum = arr[i] + arr[l] + arr[r];
          
           /*3개의 물건의 합이 C이거나 , 1개의 물건 (i,l,r)이 C 그 자체이거나,
           2개의 물건의 합이 C인 경우 (i+l)물건, (l+r)의 물건, (i+r)의 물건 */
           
           if(sum == c || arr[i] == c || arr[l] == c || arr[r] == c || 
              sum-arr[l] == c || sum - arr[i] == c || sum - arr[r] == c){
               is_able = true;
               break;
           }
           
           /*sum이 C보다 작으면 l을 키워주고 sum이 C보다 크면 r을 줄인다 */
           if(sum < c){
               l++;
           }
           else if(sum > c){
               r--;
           }
       }
         
        if(is_able == true){
            break;
        }
 
    }
    /*조합을 만족한다면 */
    if(is_able == true){
        cout << '1';
        return 0;
    }
    /*만족 못하는 경우 */
    else if(is_able == false){
        cout << '0';
        return 0;
    }
 
}