알고리즘 문제풀이/백준

백준 14500번 - 테트로미노

www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변�

www.acmicpc.net

 

하나 하나 블럭별로 나올수 있는 경우의 수를 계산하면, 각 블럭별로

2,1,8,4,4의 경우의 수가 된다. 이걸 전부 더하면 19가지의 블럭의 경우의 수가 나올수 있다. 

이걸 전부 하나씩 해봐주면된다. 

 


1
#include <iostream>
2
using namespace std;
3
int a[500][500];
4
int main() {
5
    int n, m;
6
    cin >> n >> m;
7
    for (int i=0; i<n; i++) {
8
        for (int j=0; j<m; j++) {
9
            cin >> a[i][j];
10
        }
11
    }
12
    int ans = 0;
13
    for (int i=0; i<n; i++) {
14
        for (int j=0; j<m; j++) {
15
            if (j+3 < m) {
16
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
17
                if (ans < temp) ans = temp;
18
            }
19
            if (i+3 < n) {
20
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
21
                if (ans < temp) ans = temp;
22
            }
23
            if (i+1 < n && j+2 < m) {
24
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
25
                if (ans < temp) ans = temp;
26
            }
27
            if (i+2 < n && j+1 < m) {
28
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
29
                if (ans < temp) ans = temp;
30
            }
31
            if (i+1 < n && j+2 < m) {
32
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
33
                if (ans < temp) ans = temp;
34
            }
35
            if (i+2 < n && j-1 >= 0) {
36
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
37
                if (ans < temp) ans = temp;
38
            }
39
            if (i-1 >= 0 && j+2 < m) {
40
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
41
                if (ans < temp) ans = temp;
42
            }
43
            if (i+2 < n && j+1 < m) {
44
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
45
                if (ans < temp) ans = temp;
46
            }
47
            if (i+1 < n && j+2 < m) {
48
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
49
                if (ans < temp) ans = temp;
50
            }
51
            if (i+2 < n && j+1 < m) {
52
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
53
                if (ans < temp) ans = temp;
54
            }
55
            if (i+1 < n && j+1 < m) {
56
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
57
                if (ans < temp) ans = temp;
58
            }
59
            if (i-1 >= 0 && j+2 < m) {
60
                int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
61
                if (ans < temp) ans = temp;
62
            }
63
            if (i+2 < n && j+1 < m) {
64
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
65
                if (ans < temp) ans = temp;
66
            }
67
            if (i+1 < n && j+2 < m) {
68
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
69
                if (ans < temp) ans = temp;
70
            }
71
            if (i+2 < n && j-1 >= 0) {
72
                int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
73
                if (ans < temp) ans = temp;
74
            }
75
            if (j+2 < m) {
76
                int temp = a[i][j] + a[i][j+1] + a[i][j+2];
77
                if (i-1 >= 0) {
78
                    int temp2 = temp + a[i-1][j+1];
79
                    if (ans < temp2) ans = temp2;
80
                }
81
                if (i+1 < n) {
82
                    int temp2 = temp + a[i+1][j+1];
83
                    if (ans < temp2) ans = temp2;
84
                }
85
            }
86
            if (i+2 < n) {
87
                int temp = a[i][j] + a[i+1][j] + a[i+2][j];
88
                if (j+1 < m) {
89
                    int temp2 = temp + a[i+1][j+1];
90
                    if (ans < temp2) ans = temp2;
91
                }
92
                if (j-1 >= 0) {
93
                    int temp2 = temp + a[i+1][j-1];
94
                    if (ans < temp2) ans = temp2;
95
                }
96
            }
97
        }
98
    }
99
    cout << ans << '\n';
100
    return 0;
101
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

백준 1476번 : 날짜 계산  (0) 2020.08.15
백준 3085번 - 사탕게임  (0) 2020.08.14
백준2309번 - 일곱 난쟁이  (0) 2020.08.14
백준 1316번 - 그룹단어 체커  (0) 2020.07.30
백준 7568번 - 덩치  (0) 2020.07.30