[BOJ] 샤워실 바닥 깔기 (Large)

샤워실 바닥 깔기 (Large)

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	(1 ≤ N ≤ 7)	Implementation

핵심 아이디어는 그냥 분할 정복이고, 사분면으로 나눠서 푸는 아이디어로 어디를 비워놓고 다른곳을 다 채울지 이것만 생각하면 금방 풀 수 잇는 문제인데, 약간의 구현력이 조금 따라오는거 같구요.

그리고 ㄱ 모양의 타일은 결국 정사각형의 나눠진 부분을 전부 채울 수 없고, 한칸을 비워놓을 수 밖에 없으니 그걸 어디서 합치고, 또 만약에 배수구 빼놓고 했을 때 완벽한 사각형이 등장하고, 이거 제외해서 어떻게 만들거냐! 이거를 생각만하면 solve가 가능한거 같네요

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = unsigned long long;
using ld = long double;
//ll MOD = 1'000'000'007;
ll MOD = 1'000'000'000;
//ll MOD = 1.8446744074E19;

int N, K;

int board[130][130];

int my_count;
int t1, t2;

// 그냥 사분면으로 나눠서 짤라버리면 되겠네 어차피 생긴 모양이 그래버리니까
// 사이즈가 그냥 한 변이라고 생각하고, 정사각형으로만 만든다고 생각하자
bool solution(int size, int y, int x, pair<int, int> pos){
    auto [hy, hx] = pos;
    
    if(size == 0) return false;
    
    int half = 1 << (size - 1);
    
    // 좌상, 우상, 좌하, 우하
    pair<int, int> states[] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
    
    int hole_section = 0;
    // 일단 어느 사분면에 그 hole이 있는지 찾아보자
    // pos가 비워야될 위치
    for(int i = 0; i < 4; i++){
        int qy = y + half * states[i].first;
        int qx = x + half * states[i].second;
        
        if(qy <= hy && hy < qy + half && qx <= hx && hx < qx + half){
            hole_section = i;
            break;
        }
    }
    
    pair<int, int> centers[] = {
        {y + half - 1, x + half - 1},  // 좌상
        {y + half - 1, x + half},      // 우상
        {y + half, x + half - 1},      // 좌하
        {y + half, x + half}           // 우하
    };
    
    for(int idx = 0; idx < 4; idx++){
        if(hole_section == idx) continue;
        board[centers[idx].first][centers[idx].second] = my_count;
    }
    my_count++;
    
    for(int idx = 0; idx < 4; idx++){
        int qy = y + half * states[idx].first;
        int qx = x + half * states[idx].second;
        
        if(hole_section == idx){
            solution(size-1, qy, qx, pos);
        }else{
            solution(size-1, qy, qx, centers[idx]);
        }
    }
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K;
    N = 1 << K;

    
    cin >> t1 >> t2;
    
    board[N - t2][t1 - 1] = -1;
    my_count = 1;
    solution(K, 0, 0, {N - t2,t1 - 1});
    
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout << board[i][j] << " ";
        }
        cout << "\n";
    }
    
    
    
    return 0;
}

/*
 
 0 0 0 0
 0 0 0 0
 0 0 0 0
 0 0 0 0

 
 */