9229. 한빈이와 Spot Mart D3

두 번째 글이다 ㅎㅎ;;

알고리즘 문제를 오랜만에 푸려니 머리가 잘 안돌아가기도 하고...

STL은 기본적인거 말고 죄다 까먹어 버렸다...

 

 

일단

두 번째 문제다

 

한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다.

스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다.

배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나,

과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다.

한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라.

 

 

[입력]

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.

이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 과자 봉지의 개수와 무게 합 제한을 나타내는 자연수 N, M이 주어진다.
(2 ≤ N ≤ 1000 , 2 ≤ M ≤ 2000000)

이후 N개의 줄에 각 과자봉지의 무게 가 주어진다. (1 ≤ ai ≤ 1000000)

 

[출력]

테스트 케이스마다 ‘#x’(x는 테스트 케이스 번호를 의미, 1부터 시작)를 출력하고,

한빈이가 들고 갈 수 있는 과자 봉지의 무게 합 최대를 출력하라.

 

만약 한빈이가 두 과자를 들고 갈 방법이 없는 경우에는 -1을출력한다.

 

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;
int solve(int *ARR, int MAX,int SIZE)
{
    int ret=0,temp;
    for(int i = 0;i < SIZE; i++)
    {
        for (int j = SIZE-1;j>i;j--)
        {
            if(ARR[i]+ARR[j]<=MAX){
                temp=ARR[i]+ARR[j];
                if(temp>ret)
                    ret=temp;
                if(ret==MAX){
                    return ret;
                }
            }
        }
    }
    if(ret==0)
        return -1;
    else
        return ret;
 
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int TC,N,M;
    cin>>TC;
    for (int t=1;t<=TC;t++)
    {
        cin>>N>>M;
        int *ARR = new int[N];
        for(int i=0;i<N;i++)
            cin>>ARR[i];
        sort(ARR, ARR+N);
        cout<<"#"<<t<<' '<<solve(ARR,M,N)<<'\n';
    }
    return 0;
}