AlgorithmSW역량테스트

삼성 SW 역량테스트 백준 테트로미노 14500

, , , ,

1. 삼성 SW 역량테스트 백준 감시 14500

1.1. 컴퓨팅적 사고

테트로미노의 모든 경우의 수를 구해기 위해서는 ?

(1)고려해야할 사항: 좌우 반전, 90도 회전, 반전된 것들중에 또 다시 뒤집기, 90도 회전된 것들중에 다시 뒤집기
(2) 어떻게 이것들을 최댓값을 처리할지가 가장 중요한 문제입니다.
테트로미노로 만들수 있는 경우의수는 총 19개가 만들어집니다.

하나의 예를 들어보면, n=5, m=5의 직사각형의 보드가 있다고 가정을 하겠습니다.

해당 도형:
ㅡㅡ
ㅡㅡ

보드:
ㅡ ㅡ ㅡ ㅡ ㅡ
ㅡ ㅡ ㅡ ㅡ ㅡ
ㅡ ㅡ ㅡ ㅡ ㅡ
ㅡ ㅡ ㅡ ㅡ ㅡ
ㅡ ㅡ ㅡ ㅡ ㅡ

가로의 측면:

가로의 측면으로 봤을때 m의 범위까지 만들수 있는 도형은 3개를 만들 수 있습니다.
따라서 m의 범위에 만족하는 j개수를 찾아야하는데 2,3,4의 경우가 됩니다. 이것이 어떤 말이냐하면 j의값을 몇으로 둬야지 해당 m의 범위까지 만족할 수 있는지를 찾아낼 수 있습니다.
j+2 < m 의 경우를 살펴보면, 0+2 < 5, 1+2 < 5, 2+2 < 5의 경우가 되니까 해당 가로로 되는 경우의 수를 찾을 수 있게 됩니다.

세로의측면

세로의 측면에서 봤을때 n의 범위까지 만들 수 있는 도형은 4개가 됩니다.
따라서 n의 범위를 만족하는 i의 개수를 찾아야하는데 1,2,3,4의 경우를 들 수 있습니다.
i+1 < n 의 경우를 살펴보면 0+1 < 5, 1+1 < 5, 2+1 < 5, 3+1 < 5 의 총 4가지 경우가 발생합니다.

이제 이렇게 모든 19개의 경우를 찾아준 후 Math.max함수를 사용하여 해당되는 범위를 구해줄 수 있습니다.
위의 예시를 구해보면 Math.max(비교값, board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1]) 의 경우로 해당 값들을 갱신해 나갈 수 있습니다.

따라서 이것을 점화식으로 해당되는 도형마다 모든 경우의 수를 찾아주게 되면 완전탐색을 진행할 수 있습니다.

1.2. 소스코드

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
package Samsung.ing;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 테트로미노_14500번 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //==입력==//
        int[][] map = new int[n][m];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 0;
        //==테트로미노 경우의수 찾기==//
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                /** 1
                ㅡ ㅡ ㅡ ㅡ
                 */
                if(j+3 < m){
                    answer = Math.max(answer, map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3]);
                }

                /** 2
                |
                |
                |
                |
                 */
                if(i+3 < n){
                    answer = Math.max(answer, map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j]);
                }

                /** 3
                ㅡ ㅡ
                ㅡ ㅡ
                 */
                if(i+1 < n && j+1 < m){
                    answer = Math.max(answer, map[i][j] + map[i][j+1] + map[i+1][j] + map[i+1][j+1]);
                }

                /** 4
                |
                |
                ㅡ ㅡ
                 */

                if(2+i < n && j+1 < m){
                    answer = Math.max(answer, map[i][j] + map[i+1][j] + map[i+2][j] + map[i+2][j+1]);
                }

                /** 5
                ㅡ ㅡ ㅡ
                ㅡ
                 */

                if(i+1 < n && 2+j < m){
                    answer = Math.max(answer, map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j]);
                }
                /** 6
                   |
                   |
                ㅡ ㅡ
                 */
                if(2+i < n && j+1 < m){
                    answer = Math.max(answer, map[i][j+1] + map[i+1][j+1] + map[i+2][j] + map[i+2][j+1]);
                }
                /** 7
                ㅡ ㅡ
                ㅡ
                ㅡ
                 */

                if(2+i < n && j+1 < m){
                    answer = Math.max(answer, map[i][j] + map[i][j+1] + map[i+1][j] + map[i+2][j]);
                }


                /** 8
                ㅡ
                ㅡ ㅡ ㅡ
                 */
                if(i+1 < n && j+2 < m){
                    answer = Math.max(answer, map[i][j] + map[i+1][j] + map[i+1][j+1] + map[i+1][j+2]);
                }
                /** 9
                ㅡ ㅡ
                   |
                   |
                 */
                if(i+2 < n && j+1 < m){
                    answer = Math.max(answer, map[i][j] + map[i][j+1] + map[i+1][j+1] + map[i+2][j+1]);
                }

                /** 10
                   ㅡ ㅡ
                ㅡ ㅡ
                 */

                if(i+1 < n && j+2 < m) {
                    answer = Math.max(answer, map[i][j + 1] + map[i][j + 2] + map[i + 1][j] + map[i + 1][j + 1]);
                }
                /** 11
                ㅡ
                ㅡ ㅡ
                   ㅡ
                 */
                if(i+2 < n && j+1<m){
                    answer = Math.max(answer, map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1]);
                }
                /** 12
                    ㅡ
                 ㅡ ㅡ
                 ㅡ
                 */
                if(i+2 < n && j+1<m){
                    answer = Math.max(answer, map[i][j+1]+map[i+1][j]+map[i+1][j+1]+map[i+2][j]);
                }
                /** 13
                ㅡ ㅡ
                   ㅡ ㅡ
                 */
                if(i+1<n && j+2<m){
                    answer = Math.max(answer , map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2]);
                }
                /** 14
                   |
                ㅡ ㅡ ㅡ
                 */
                if(i+1 < n && j+2 < m){
                    answer = Math.max(answer, map[i][j+1]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]);
                }
                /** 15
                |
                | ㅡ
                |
                 */

                if(i+2<n && j+1<m){
                    answer = Math.max(answer, map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j]);
                }

                /** 16
                ㅡ ㅡ ㅡ
                   |
                 */
                if(i+1 < n && j+2 < m){
                    answer = Math.max(answer, map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+1]);
                }
                /** 17
                   |
                 ㅡ |
                   |
                 */

                if(i+2<n && j+1<m){
                    answer = Math.max(answer,map[i][j+1]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1]);
                }

                /** 18
                 * ㅡ ㅡ ㅡ
                 *      |
                 */

                if(i+1 < n && j+2 < m){
                    answer = Math.max(answer, map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2]);
                }
                /** 19
                 *      |
                 * ㅡ ㅡ ㅡ
                 */
                if(i+1 < n && j+2 < m){
                    answer = Math.max(answer, map[i][j+2]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]);
                }
            }
        }
        System.out.println(answer);
   }
}

Share