티스토리 뷰

문제 링크입니다.

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누

www.acmicpc.net

 

풀이 방법

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

 

테트로미노는 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;
}

'Dev.CodingTest > BACKJOON' 카테고리의 다른 글

[백준 c++] 14502번 : 연구소  (0) 2020.04.26
[백준 c++] 14501번 : 퇴사  (2) 2020.04.26
[백준 c++] 14499번 : 주사위 굴리기  (0) 2020.04.25
[백준 c++] 13458번 : 시험 감독  (0) 2020.04.25
[백준 c++] 3190번 : 뱀  (0) 2020.04.25
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함