[C++] 백준 14500번

테트로미노 👾

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

👀  정사각형은 서로 겹치면 안 된다.

👃🏻  도형은 모두 연결되어 있어야 한다.

👅  정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 5가지 모양이 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다~.~

 

main.cpp

//
//  main.cpp
//  Implementation
//
//  Created by Sun on 2023/03/30.
//

#include <iostream>
#include <algorithm>	// for max...

int maxElem(int row, int col, int *ptrArr) {    // 2차원 배열 ~x~의 최댓값 반환
    int maxVal = 0;

    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            maxVal = std::max(maxVal, *((ptrArr + i * col) + j));
        
    return maxVal;
}

int main(int argc, const char * argv[]) {

    int N, M;
    std::cin >> N >> M;

    int paper[N][M];    // 종이에 적힌 수
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::cin >> paper[i][j];
        }
    }

    // 4x1 filter
    int fourXone[N-4+1][M-1+1];
    for (int i = 0; i < N-4+1; i++) {
        for (int j = 0; j < M-1+1; j++) {
            fourXone[i][j] = 0;
            for (int k = 0; k < 4; k++)
                fourXone[i][j] += paper[i+k][j];
        }
    }
    // 1x4 filter
    int oneXfour[N-1+1][M-4+1];
    for (int i = 0; i < N-1+1; i++) {
        for (int j = 0; j < M-4+1; j++) {
            oneXfour[i][j] = 0;
            for (int k = 0; k < 4; k++)
                oneXfour[i][j] += paper[i][j+k];
        }
    }
    // 2x3 filter
    int twoXthree[N-2+1][M-3+1];
    for (int i = 0; i < N-2+1; i++) {
        for (int j = 0; j < M-3+1; j++) {
            twoXthree[i][j] = 0;
            int W3 = 0, S1 = 0, W1 = 0, S3 = 0;     // WASD 기준 n칸 -> Xn
            for (int m = 0; m < 3; m++) {
                W3 += paper[i][j+m];                   // 3칸 모두 포함
                S1 = std::max(S1, paper[i+1][j+m]);     // max 1칸 포함
                W1 = std::max(W1, paper[i][j+m]);
                S3 += paper[i+1][j+m];
            }
            int ZorO = paper[i][j+1] + paper[i+1][j+1];     // Z모양 or ㅁ모양
            ZorO += std::max(paper[i][j], paper[i][j+2]);     // 가운데 블록은 무조건 포함
            ZorO += std::max(paper[i+1][j], paper[i+1][j+2]);   // 나머지 중에 선택
            
            twoXthree[i][j] = std::max({W3+S1, W1+S3, ZorO});
        }
    }
    // 3x2 filter
    int threeXtwo[N-3+1][M-2+1];
    for (int i = 0; i < N-3+1; i++) {
        for (int j = 0; j < M-2+1; j++) {
            threeXtwo[i][j] = 0;
            int A3 = 0, D1 = 0, A1 = 0, D3 = 0;     // WASD 기준 n칸 -> Xn
            for (int m = 0; m < 3; m++) {
                A3 += paper[i+m][j];
                D1 = std::max(D1, paper[i+m][j+1]);
                A1 = std::max(A1, paper[i+m][j]);
                D3 += paper[i+m][j+1];
            }
            int ZorO = paper[i+1][j] + paper[i+1][j+1];     // Z모양 or ㅁ모양
            ZorO += std::max(paper[i][j], paper[i+2][j]);
            ZorO += std::max(paper[i][j+1], paper[i+2][j+1]);
            
            threeXtwo[i][j] = std::max({A3+D1, A1+D3, ZorO});
        }
    }
    
    std::cout << std::max({maxElem(N-3+1, M-2+1, (int*)threeXtwo),
                        maxElem(N-2+1, M-3+1, (int*)twoXthree),
                        maxElem(N-4+1, M-1+1, (int*)fourXone),
                        maxElem(N-1+1, M-4+1, (int*)oneXfour)}) << std::endl;

    return 0;
}

꺅ㄱ

어떤 4개를 골라도 연결"이라는 건 오타고... 안되는 모양이 이씀

 

2차원 배열을 함수에 전달하고 싶다,,,,는 심플한 요구가 오늘따라 넘 어려워서.......2차원 배열 포인터와 포인터 배열을 이해하기 위해 한 100개가 넘는 글들을 본 것 같다. 그 중 도움이 됐거나 될 예정인 것들.......

이차원배열을 매개변수로 넣어주기 (passing a 2d array as a function argument)

Correct way of passing 2 dimensional array into a function

진짜 이차원배열처럼 malloc하는 방법

C++ 2차원 포인터(포인터의 포인터)를 이용한 2차원 배열 다루기

일단 구현(브루트포스...)유형답게 풀긴했는데 넘 노가다 느낌이 강해서 나중에 dfs로 다시 풀어보도록 하겠당~