카테고리 없음

백준 2115번 갤러리 (C++)

문제 링크

문제

그림이 2칸짜리 선인데, 벽과 빈 공간 사이에 그림을 겹치지 않게 최대 몇 개나 걸 수 있는지 알아내는 문제이다.

 

 

풀이

그림을 거는 방향에 따라 벽과 빈공간의 패턴을 4가지로 나눌 수 있다.

// 왼쪽
X.
X.

// 위
XX
..

// 오른쪽
.X
.X

// 아래
..
XX

같은 벽에 그림을 놓을 때 한쪽 끝부터 그림을 꽉꽉 채워서 걸면 항상 가장 많이 걸 수 있다. 각각의 패턴에서 그림을 최대한 많이 걸어 보고 그 갯수를 구해서 더하면 된다. 

 

그림을 겹치게 걸면 안되기 때문에 그림을 건 곳을 배열에 따로 표시하고 그곳은 나중에 패턴 검사를 건너뛴다.

 

 

구현

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <string>

using namespace std;

#define RANGE(x, n) (int x = 0; x < n; x++)
#define FASTIOS ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define DEBUG(x) cerr<<#x<<" = "<<x<<'\n'

#ifdef BOJ
#define endl "\n"
#endif

typedef long long ll;
constexpr int INF = 0x3ffffffe;

typedef vector<vector<int> > Pattern;

vector<Pattern> patterns = {
    {
        {'.', '.'},
        {'X', 'X'},
    },
    {
        {'X', '.'},
        {'X', '.'},
    },
    {
        {'X', 'X'},
        {'.', '.'},
    },
    {
        {'.', 'X'},
        {'.', 'X'},
    },
    
};

vector<string> field;
void solve(int tc = 0) {
    int n, m;
    cin >> n >> m;

    field.resize(n);
    for RANGE(i, n) {
        cin >> field[i];
    }

    

    auto scan = [&](Pattern& patt) -> int {
        vector<vector<bool> > picked;
        picked.assign(n, vector<bool>(m, false));

        auto match = [&](int y, int x, int size=2) -> bool {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (field[y+i][x+j] != patt[i][j]) {
                        return false;
                    }
                }
            }
            return true;
        };

        auto pick = [&picked](int y, int x, int size=2) -> void {
            for (int i = 0; i < size; i++) {
                for (int j = 0 ; j < size; j++) {
                    picked[y+i][x+j] = true;
                }
            }
        };

        int ret = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                if (!picked[i][j] && match(i, j)) {
                    pick(i, j);
                    ret++;
                }
            }
        }


        
        return ret;
    };

    int ret = 0;
    for (auto& patt : patterns) {
        ret += scan(patt);
    }
    cout << ret << endl;
}

int main() {
    FASTIOS

    solve();
}

패턴 검사와 그림 건 곳 표시할때 반복문이 너무 많아져 C++ 람다 함수를 적극 활용해 코딩해보았다.

 

Tekiter