포스트

BOJ 14500. 테트로미노

Problem Solving
게시 수정 작성자 August
좋아요 조회 10 분 읽는 시간
  • 문제링크 : https://www.acmicpc.net/problem/14500

문제 요약

테트로미노는 1×1 정사각형 네 개를 변끼리 이어 붙인 도형으로, 모양이 다섯 가지 있다. N×M 종이의 각 칸에 정수가 적혀 있을 때, 테트로미노 하나를 회전하거나 뒤집어서 종이 위에 놓아 덮인 네 칸의 합이 최대가 되게 하고 그 합을 구한다.

1. 문제해석

우선, 주어진 테트로미노를 회전, 대칭하여 만들 수 있는 테트로미노는 1+2+4+4+8=19로 총 19개이다.

그러면 한 개씩 종이 칸에 테트로미노를 하나씩 놓아보면서 합이 가장 큰 것을 구하기 위해서는 브루트 포스로 하나씩 다 맵핑해 보아야 한다. 아래와 같은 경우에 시간 복잡도는 가로가 N, 세로가 M이라고 하면 (N-3)x(M-3)이지만 N,M이 커지면 O(NxM)이 된다. 19개를 모두 해 보아야 하므로, 19xNxM이지만 19는 N과 M에 비해 매우 작기때문에 총 시간복잡도는 O(NxM)이다.

여기서 N과 M은 500을 넘지 않으므로, 충분한 시간안에 브루트 포스로 풀이가 가능하다.


<hr />

2. 문제 풀이

19개의 각 테트로미노의 모양은 고정이므로 직접 다 입력해주는 방법으로 구현한다. 그리고 정수가 쓰여진 맵을 이차원 배열로 받아서, 범위를 넘지않도록 맵핑하고 반복하면서 최댓값을 찾는다. 각 테트로미노에 따라 범위 제한은 달라질 것이다. 위의 그림처럼 검은색 점 부분만 반복하면 된다고 생각할 수 있다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <iostream>
using namespace std;

int map[1000][1000];

int main(){
    int N,M;
    cin >> N >> M;
    int answer=0;
    
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            cin >> map[i][j];
        }
    }    
    for(int i=0;i<N;++i){ // type 1
        for(int j=0;j<M-3;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3];
        }
    }
    for(int i=0;i<N-3;++i){
        for(int j=0;j<M;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 2
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1];
        }
    }
    
    for(int i=0;i<N-2;++i){ // type 3
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){ // type 3 - symmatric
        for(int j=0;j<M-1;++j){
            if(map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j] > answer)
                answer=map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-2;++i){ // type 4
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1] > answer)
                answer=map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 5
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1];
        }
    }
    cout << answer << "\n";
    return 0;
}

처음에는 위와 같이 반복문에서 반복횟수를 제한함으로써 범위를 제한했다. 하지만 이러한 방법으로는 실수가 너무 잦았고, 코드가 길어지는 불편함이 있었다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include <iostream>
using namespace std;
int a[500][500];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (j+3 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
                if (ans < temp) ans = temp;
            }
            if (i+3 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2];
                if (i-1 >= 0) {
                    int temp2 = temp + a[i-1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (i+1 < n) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
            }
            if (i+2 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j];
                if (j+1 < m) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (j-1 >= 0) {
                    int temp2 = temp + a[i+1][j-1];
                    if (ans < temp2) ans = temp2;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이와 같이, 하나의 반복문에서 if문으로 제한을 두는게 조금 더 보기에 편했다.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {	// 19개의 테트로미노를 미리 정의
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (int k=0; k<19; k++) {
                bool ok = true;
                int sum = a[i][j];
                for (int l=0; l<3; l++) {
                    int x = i+block[k][l][0];
                    int y = j+block[k][l][1];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        sum += a[x][y];
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (ok && ans < sum) {
                    ans = sum;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이렇게 코드를 간편화할 수도 잇겠지만, 실전에서는 실력에 맞게 직접 맵핑하는 방식을 사용하는 것이 맞는 것 같다. 코드가 직관적일수록 이해도 빠르고 디버깅도 쉽기 때문이다.

ProblemSolving, BOJ
BOJ Brute Force Simulation
이 글은 저작권자의 CC BY 4.0 라이선스를 따릅니다.

변경이력

2번 수정

  1. docs(posts): separate the sections of every post with a thematic break
  2. docs(problemsolving): replace copied problem statements with summaries

댓글

아직 댓글이 없습니다