[백준] 16937 - 두 스티커 (C++)

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

 

크기가 H × W인 모눈종이에 크기가 Ri × Ci인 스티커 N개 중 2개를 최대한 넓게 붙이는 문제다.

두 스티커는 겹쳐질 수 없고 모눈종이를 벗어날 수 없으며, 두 스티커가 접하는 것과 스티커를 90도 회전시키는 것은 가능하다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

입출력 제한이 작아서 브루트 포스로 먼저 시도해보는 게 좋을 듯하다. (+ int 범위 안에서 해결 가능)

 

N개 중 하나를 골라 모눈종이에 붙인 뒤 모눈종이를 벗어나지 않는지 확인한다. 모눈종이를 벗어난다면 불가능하므로 고른 스티커를 회전시켜 계속해서 확인한다. 조건이 맞는다면 N-1개의 스티커 중 하나를 골라 빈 공간에 들어갈 수 있는지 확인한다. 들어갈 수 없다면 스티커를 회전시켜 계속해서 확인한다.

 

스티커는 직사각형 모양만 존재하므로 복잡하게 생각할 필요는 없다. 스티커를 90도 회전시키는 경우 직사각형 모양 2개만 고려하면 된다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. H, W, N, Ri, Ci 입력 받기
2. Ri와 Ci가 H와 W를 넘지 않는 스티커만 vector에 넣기 (총 개수가 2개 미만이면 0 return하고 종료)
3. vector에 있는 스티커 중 하나를 골라 모눈종이에 붙이고 남는 공간의 최대 크기 확인하기 (회전시킨 값도 고려)
4. 들어갈 수 있는 스티커를 확인하고, 붙인 넓이를 계산해 mx 값보다 크면 갱신하기
5. 4~5 반복
6. mx 출력하고 종료

1. H, W, N, Ri, Ci 입력 받기
2. Ri와 Ci가 H와 W를 넘지 않는 스티커만 vector에 넣기
3. vector에서 스티커 2개를 골라 모눈종이에 붙일 수 있는지 확인 - 첫 번째와 두 번째 스티커가 각각 회전하는 경우와 두 번째 스티커가 첫 번째 스티커의 오른쪽 또는 아래에 붙는 경우(총 8가지)를 조건문으로 검사
4. 3번을 vs*(vs-1)만큼 반복 (vs: vector size)
5. mx 출력한 뒤 종료

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1~3회차

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define pii pair<int,int>

int h,w,n,r,c,mx;
vector<pii> v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> h >> w >> n;
    for (int i=0; i<n; i++) {
        cin >> r >> c;
        if (r<=h && c<=w || r<=w && c<=h)
            v.push_back({r,c});
    }

    int vs = v.size();
    if (vs < 2) {
        cout << 0;
        return 0;
    }

    for (int i=0; i<vs; i++) {
        auto [a,b] = v[i];
        int xx[4] = {h,w,h,w}, yy[4] = {(w-b), (w-a), (w-b), (w-a)};
        for (int j=i+1; j<vs; j++) {
            auto [x,y] = v[j];
            for (int k=0; k<4; k++) {
                if (x<=xx[k] && y<=yy[k] || x<=yy[k] && y<=xx[k]) {
                    mx = max(mx, a*b+x*y);
                }
            }
        }
    }

    cout << mx;
}

• yy 배열에 인자를 잘못 넣음
• vector에 넣는 조건을 잘못 만듦
• 로직 수정 🥲

 

---

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define pii pair<int,int>

int h,w,n,r,c,mx;
vector<pii> v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> h >> w >> n;
    for (int i=0; i<n; i++) {
        cin >> r >> c;
        if (r<=h && c<=w || r<=w && c<=h)
            v.push_back({r,c});
    }

    int vs = v.size();
    for (int i=0; i<vs; i++) {
        for (int j=i+1; j<vs; j++) {
            auto [r1,c1] = v[i];
            auto [r2,c2] = v[j];
            if (r1+r2 <= h && max(c1,c2) <= w || max(r1,r2) <= h && c1+c2 <= w)
                mx = max(mx, r1*c1+r2*c2);
            else if (r1+c2 <= h && max(c1,r2) <= w || max(r1,c2) <= h && c1+r2 <= w)
                mx = max(mx, r1*c1+r2*c2);
            else if (c1+r2 <= h && max(r1,c2) <= w || max(c1,r2) <= h && r1+c2 <= w)
                mx = max(mx, r1*c1+r2*c2);
            else if (c1+c2 <= h && max(r1,r2) <= w || max(c1,c2) <= h && r1+r2 <= w)
                mx = max(mx, r1*c1+r2*c2);
        }
    }

    cout << mx;
}