[Algorithm] 백준 - 두 스티커 (16937번)

문제

[백준] 두 스티커

16937번: 두 스티커

 

사용 알고리즘

- 구현

해결방법

• 모눈 종이에 두 스티커를 붙이는 방법은 2가지다
  • 가로로(옆으로) 나란히 붙이기
  • 세로로(위아래로) 나란히 붙이기
• 이 때, 신경써야 하는 부분은 각각의 방법으로 붙였을 때 모눈종이를 벗어나는지이다
  • 가로로 붙이는 경우
    • A가로길이 + B가로길이 <= 모눈의 가로
    • max(A높이, B높이) <= 모눈의 세로
  • 세로로 붙이는 경우
    • A세로길이 + 세로길이 <= 모눈의 세로
    • max(A가로, B가로) <= 모눈의 가로

스티커를 붙이는 2가지 방법

• 가로 또는 세로로 붙일 수 있다는 점을 파악했으면, 그 다음으로 주의할 점은 스티커가 직사각형이란 점이다. 가로,세로 길이가 다르므로 A와 B스티커를 나란히 붙인다는건 총 4가지 모양이 나올 수 있다.
  • A원본, B원본
  • A를 90도 회전, B원본
  • A원본, B를 90도 회전
  • A를 90도 회전, B를 90도 회전
• 위의 모든 경우를 다 생각하면 총 8가지가 된다! (가로|회전4경우, 세로|회전4경우)
• 모든 경우를 다 보면서 두 스티커가 모눈종이를 벗어나지 않으면서 최대의 넓이를 갖는 경우를 구하면 된다

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int H, W, n;
typedef pair<int, int> stk; // pair<가로, 세로>

bool check_stk(stk s1, stk s2) {
    // 원본
    if (max(s1.second, s2.second) <= H && (s1.first + s2.first) <= W) return true;
    if (max(s1.first, s2.first) <= W && (s1.second + s2.second) <= H) return true;

    // 1번 회전
    if (max(s1.first, s2.second) <= H && (s1.second + s2.first) <= W) return true;
    if (max(s1.second, s2.first) <= W && (s1.first + s2.second) <= H) return true;

    // 2번 회전
    if (max(s1.second, s2.first) <= H && (s1.first + s2.second) <= W) return true;
    if (max(s1.first, s2.second) <= W && (s1.second + s2.first) <= H) return true;

    // 둘 다 회전
    if (max(s1.first, s2.first) <= H && (s1.second + s2.second) <= W) return true;
    if (max(s1.second, s2.second) <= W && (s1.first + s2.first) <= H) return true;

    return false;
}
 
// BOJ 16937 두 스티커
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> H >> W;
    cin >> n; // 스티커
 
    vector<stk> stv;
 
    int x, y;
    for (int i=0; i<n; i++) {
        cin >> x >> y;
 
        // 스티커가 모눈종이보다 큰 경우
        if (max(x, y) > max(H, W)) continue;
 
        stv.push_back(make_pair(x, y));
    }

    int result = 0;
    for (int i = 0; i < stv.size(); i++) {
        for (int j = i+1; j < stv.size(); j++) {
            if (check_stk(stv[i], stv[j])) {
                int width = stv[i].first*stv[i].second + stv[j].first*stv[j].second;
                result = max(result, width);
            }
        }
    }

    cout << result;
 
    return 0;
}

 

참고 블로그

https://yabmoons.tistory.com/278

 

한줄평

처음엔 이 문제를 스티커의 회전경우를 각각 다른 스티커로 취급하고 조합문제처럼 풀었다. 벡터를 써서. 그랬더니 자꾸 답이 틀렸다는 것이다. ㅠㅠ 아무래도 조합을 찾다가 먼가 무한루프로 빠진 것 같은데. . 두 스티커의 가로, 세로 길이를 모눈종이와 비교만 하면 된다는 포인트를 못 찾으면 많이 해매게 되는 문제 같다.