본문 바로가기
알고리즘/백준

[백준] 14500번 테트로미노

여우와펭귄 2019. 10. 3. 15:42
반응형

14500번 테트로미노

1. 이해하기

  • 가능한 테트로미노 5가지 모양을 종이 위에 놓아보며 테트로미노가 놓은 칸의 수들의 합의 최대를 구하는 문제.
  • 테트로미노가 놓여질 수 있는 방법을 모두 구해서 값을 비교해보는 완전탐색 문제.

2. 구현하기

  • 각 모양마다 나올 수 있는 방법을 모두 구해 합을 반환하는 함수

    int get_max_sum(int x, int y) {
    int sum = 0;
    if(y+3 < M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x][y+3];
        sum = max(sum,temp);
    }
    if(x+3 < N) {
        int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+3][y];
        sum = max(sum,temp);
    }
    if(x+1 < N and y+1 < M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y]+map[x+1][y+1];
        sum = max(sum,temp);
    }
    if(x+2 < N and y+1 < M) {
        int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+2][y+1];
        sum = max(sum,temp);
        temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x+2][y+1];
        sum = max(sum,temp);
    }
    if(x+1 < N and y+2 < M) {
        int temp = map[x][y]+map[x+1][y]+map[x][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x-1>=0 and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x-1][y+2];
        sum = max(sum,temp);
    }
    if(x-2>=0 and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x-2][y+1];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y]+map[x+2][y];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+2][y+1];
        sum = max(sum,temp);
    }
    if(x-1>=0 and x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x-1][y+2];
        sum = max(sum,temp);
    }
    if(x-2>=0 and y+1<M) {
        int temp = map[x][y]+map[x-1][y]+map[x-1][y+1]+map[x-2][y+1];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x-1>=0 and x+1<N and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x+1][y+1];
        sum = max(sum,temp);
    }
    if(x-1>=0 and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+2][y];
        sum = max(sum,temp);
    }

    return sum;
}

  1. 전체 코드

    #include <iostream>
using namespace std;
int map[500][500];
int N,M;

int get_max_sum(int x, int y) {
    int sum = 0;
    if(y+3 < M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x][y+3];
        sum = max(sum,temp);
    }
    if(x+3 < N) {
        int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+3][y];
        sum = max(sum,temp);
    }
    if(x+1 < N and y+1 < M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y]+map[x+1][y+1];
        sum = max(sum,temp);
    }
    if(x+2 < N and y+1 < M) {
        int temp = map[x][y]+map[x+1][y]+map[x+2][y]+map[x+2][y+1];
        sum = max(sum,temp);
        temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x+2][y+1];
        sum = max(sum,temp);
    }
    if(x+1 < N and y+2 < M) {
        int temp = map[x][y]+map[x+1][y]+map[x][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x-1>=0 and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x-1][y+2];
        sum = max(sum,temp);
    }
    if(x-2>=0 and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x-2][y+1];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y]+map[x+2][y];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x][y+2]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+2][y+1];
        sum = max(sum,temp);
    }
    if(x-1>=0 and x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x-1][y+2];
        sum = max(sum,temp);
    }
    if(x-2>=0 and y+1<M) {
        int temp = map[x][y]+map[x-1][y]+map[x-1][y+1]+map[x-2][y+1];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x+1][y+2];
        sum = max(sum,temp);
    }
    if(x+1<N and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x+1][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x-1>=0 and x+1<N and y+1<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x+1][y+1];
        sum = max(sum,temp);
    }
    if(x-1>=0 and y+2<M) {
        int temp = map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x][y+2];
        sum = max(sum,temp);
    }
    if(x+2<N and y+1<M) {
        int temp = map[x][y]+map[x+1][y]+map[x+1][y+1]+map[x+2][y];
        sum = max(sum,temp);
    }

    return sum;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            ans = max(ans,get_max_sum(i,j));
        }
    }
    cout << ans << '\n';
    return 0;
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 14502번 연구소  (0) 2019.10.03
[백준] 14501번 퇴사  (0) 2019.10.03
[백준] 14499번 주사위 굴리기  (0) 2019.10.03
[백준] 13458번 시험 감독  (0) 2019.10.03
[백준] 3190번 뱀  (0) 2019.10.03

'알고리즘/백준' Related Articles

티스토리툴바