문제1.

풀이

• 이 문제는 c1,c2,c3 모든 조합에 대해 3중 for문으로 가능한 target이 있는지 확인할 수 있으나, 이렇게 하면 시간복잡도가 O(N^3)이 되므로 너무 크다.
• 그래서 3중 for문을 돌되, 한 target t에 대해, c1, c2를 탐색하며 bianry_search로 가능한 c3가 cards 벡터에 존재하는지 찾아 O(N^2log2)로 시간복잡도를 낮췄다.
• 만약 c3가 cards에 있다면 가장 바깥 for문의 target t는 가능한 t이므로 possible 플래그를 true로 설정하여 break로 c1,c2의 2중 for문을 탈출하도록 해 시간복잡도를 낮췄다.
• 이때 binary_search는 algorithm 라이브러리의 binary_search메소드를 사용해 cards.begin(), cards.end(), c3를 전달해서 찾아주면 빠르게 bool 값을 얻을 수 있다.
• 또한 가능한 당첨번호가 여러개라면 오름차순 정렬해 출력하라고 했으므로 algorithm 라이브러리의 sort()메소드에 result.begin(), result.end()를 전달해서 정렬해준다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> getPossibleTarget(vector<int>& cards, const vector<int>& targets) {

    vector<int> possibleTarget;//가능한 당첨번호 저장 벡터
    sort(cards.begin(), cards.end());//card 배열 시작위치,끝위치 인자 오름차순 정렬

    for (int i = 0; i < targets.size(); i++) {
        //1. 한 target t에 대해
        int t = targets[i];
        bool possible = false;

        //2. 정렬된 card 배열 탐색, c1와
        for (int j = 0; j < cards.size(); j++) {
            int c1 = cards[j];

            //3. c2에 대해
            for (int k = 0; k <= j; k++) {
                int c2 = cards[k];

                //t == (c1+c2) + c3 되는 c3를 구하고
                int c3 = t - (c1 + c2);
                //바이너리 서치로 c3를 cards에서 찾아 있으면 플래그 세우고, break
                if (binary_search(cards.begin(), cards.end(), c3) == true) {
                    possible = true;
                    break;
                }
            }
            //4. c1에 대한 c2 탐색 종료 후 있으면, 이번 target은 가능이므로 탈출
            if (possible) {
                break;
            }
        }
        //탈출해서 해당 target(t)를 가능 벡터에 저장
        if (possible) {
            possibleTarget.push_back(t);
        }
    }

    //최종 결과를 정렬해 반환
    sort(possibleTarget.begin(), possibleTarget.end());
    return possibleTarget;
}

int main() {

    //사용할 카드 수 n, 당첨 번호의 숫자 m 입력
    int n, m;
    cin >> n >> m;

    //n개의 카드에 적힌 수 입력
    vector<int> cards(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }

    //m개의 당첨 번호 입력
    vector<int> targets(m);
    for (int i = 0; i < m; i++) {
        cin >> targets[i];
    }

    //세카드 합으로 가능한 당첨번호 벡터 반환
    vector<int> result = getPossibleTarget(cards, targets);

    if (result.empty()) {//없으면 no
        cout << "NO" << endl;
    }
    else {//있으면 결과 출력
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
    }

    return 0;
}

문제2. 직사각형

풀이

• 이 문제는 직사각형의 대각선 좌표 두개를 사용해서 left, right, top, bottom 값을 구하면 쉽게 해결할 수 있다.
• 직1의 l1,r1,t1,b1와 직2의 l2,r2,t2,b2 정보를 사용해서 교차된 직사각형의 넓이를 구하려면, 중앙으로 모여야 하므로 l은 오른쪽으로, r은 왼쪽으로, t는 아래쪽으로, b는 위쪽으로 좌표를 선정해야 한다.
• 이렇게 선정한 l,r,t,b 정보가 l<=r && b<=t인 경우에는 넓이가 유효하므로 이를 계산해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int get_area(int l1, int r1, int t1, int b1, int l2, int r2, int t2, int b2) {
    
    //구할 직사각형 
    int l, r, t, b;

    l = max(l1, l2);
    r = min(r1, r2);
    t = min(t1, t2);
    b = max(b1, b2);
    
    //길이이므로 음수나오면 안되니까 조건 검사 후
    if (l <= r && b <= t) {
        return (r - l) * (t - b);//밑변*높이 리턴
    }   
}

void test_case() {
    //직사각형1 대각선 두 점 x,y좌표,
    int ax, ay, bx, by;
    //직사각형2 대각선 두 점 x,y좌표 입력
    int px, py, qx, qy;
    cin >> ax >> ay >> bx >> by >> px >> py >> qx >> qy;

    //직사각형1 계산
    int l1, r1, t1, b1;
    l1 = min(ax, bx);//왼쪽 x좌표
    r1 = max(ax, bx);//오른쪽 x좌표
    t1 = max(ay, by);//위 y좌표
    b1 = min(ay, by);//아래 y좌표

    //직사각형2 계산
    int l2, r2, t2, b2;
    l2 = min(px, qx);//왼쪽 x좌표
    r2 = max(px, qx);//오른쪽 x좌표
    t2 = max(py, qy);//위 y좌표
    b2 = min(py, qy);//아래 y좌표

    //넓이 반환
    int result = get_area(l1, r1, t1, b1, l2, r2, t2, b2);

    //넓이 출력
    cout << result << endl;
}

int main() {
    
    //테스트케이스 t 입력
    int t;
    cin >> t;
    
    //t개의 테스트 케이스에 4점x,y 좌표 총 8개 입력
    for (int i = 0; i < t; i++) {
        test_case();
    }
   
    return 0;
}