[백준 c++] 14500번 테트로미노

문제 링크입니다.

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

14500번: 테트로미노

 

풀이 방법

브루트포스 알고리즘을 사용합니다.

 

테트로미노는 5개의 모양를 가지지만 상하좌우 방향을 달리함에 따라 19개의 모양을 가집니다.

이러한 19개의 모양을 shape 배열에 저장해놓고,

모든 칸을 순회하며 각 칸에 19개의 모양을 대입합니다.

 

순회를 진행하면서 각 모양마다 속한 칸의 숫자들을 더하고 비교 연산을 통해 최댓값을 구합니다.

 

풀이 

//
//  main.cpp
//  14500
//
//  Created by Jihye on 2020/04/26.
//  Copyright © 2020 Jihye Han. All rights reserved.
//

#include <iostream>

using namespace std;

int n, m; // 행, 열의 크기
int board[500][500]; // 종이
int ans = 0; // 최대합

const int shape[19][4][2] = {
    { {0,0}, {0,1}, {1,0}, {1,1} },
    { {0,0}, {0,1}, {0,2}, {0,3} },
    { {0,0}, {1,0}, {2,0}, {3,0} },
    { {0,0}, {0,1}, {0,2}, {1,0} },
    { {0,2}, {1,0}, {1,1}, {1,2} },
    { {0,0}, {1,0}, {1,1}, {1,2} },
    { {0,0}, {0,1}, {0,2}, {1,2} },
    { {0,0}, {1,0}, {2,0}, {2,1} },
    { {0,0}, {0,1}, {1,1}, {2,1} },
    { {0,0}, {0,1}, {1,0}, {2,0} },
    { {0,1}, {1,1}, {2,0}, {2,1} },
    { {0,0}, {1,0}, {1,1}, {2,1} },
    { {0,1}, {1,0}, {1,1}, {2,0} },
    { {0,1}, {0,2}, {1,0}, {1,1} },
    { {0,0}, {0,1}, {1,1}, {1,2} },
    { {0,0}, {0,1}, {0,2}, {1,1} },
    { {0,1}, {1,0}, {1,1}, {1,2} },
    { {0,1}, {1,0}, {1,1}, {2,1} },
    { {0,0}, {1,0}, {1,1}, {2,0} }
};

void tetromino(int x, int y) {
    // 19개의 테트로미노 모양 대입하기
    for (int i = 0; i < 19; i++) {
        int temp = 0;
        for (int j = 0; j < 4; j++) {
            int tx = x + shape[i][j][0];
            int ty = y + shape[i][j][1];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                temp += board[tx][ty];
            }
        }
        if (ans < temp) ans = temp;
    }
}

void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            tetromino(i, j);
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &board[i][j]);
        }
    }
    
    solve();
    
    return 0;
}