백준 16937 두 스티커

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

16937번: 두 스티커

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int h, w;
    int n;
    vector<pair<int, int>> st;      //각 스티커의 크기

    int ans = 0;

    cin >> h >> w;

    cin >> n;

    for (int i = 0; i < n; i++) {
        int r, c;
        cin >> r >> c;

        st.push_back(make_pair(r, c));
    }


    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {

            int curh, curw;


            //주어진 그대로 붙이는 경우
                curh = st[i].first + st[j].first;
                curw = max(st[i].second, st[j].second);


                //가로로 이어 붙이는 경우
                if (curh <= h && curw <= w) {
                    ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
                }


                curh = max(st[i].first, st[j].first);
                curw = st[i].second + st[j].second;
                //세로로 이어붙이는 경우
                if (curh <= h && curw <= w) {
                    ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
                }

            //i번 스티커만 회전하는 경우
            curh = st[i].second + st[j].first;
            curw = max(st[i].first, st[j].second);


            //가로로 이어 붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }


            curh = max(st[i].second, st[j].first);
            curw = st[i].first + st[j].second;
            //세로로 이어붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }

            //j번 스티커만 회전하는 경우

            curh = st[i].first + st[j].second;
            curw = max(st[i].second, st[j].first);


            //가로로 이어 붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }


            curh = max(st[i].first, st[j].second);
            curw = st[i].second + st[j].first;
            //세로로 이어붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }

            //두 스티커 모두 회전하는 경우


            curh = st[i].second + st[j].second;
            curw = max(st[i].first, st[j].first);


            //가로로 이어 붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }


            curh = max(st[i].second, st[j].second);
            curw = st[i].first + st[j].first;
            //세로로 이어붙이는 경우
            if (curh <= h && curw <= w) {
                ans = max(ans, st[i].first*st[i].second+st[j].first*st[j].second);
            }



        }
    }

    cout << ans;




    return 0;
}

 

스티커를 입력받은 뒤 각 케이스로 나누어 풀이한다.

    - 스티커는 90도 회전할 수 있으므로 i번 스티커를 회전하는 경우와 회전하지 않는 경우, j번 스티커를 회전하는 경우와          회전하지 않는 경우로 나눈다.

    - 두 스티커를 가로로 붙이는 경우, 세로로 붙이는 경우를 나눈다.

 

 

 각 스티커당 위의 총 8개 경우의 수를 계산하여 총 길이가 모눈종이를 벗어나지 않는 경우 넓이를 계산한다. 모든 경우 중 최댓값이 정답으로 출력된다.