문제
테트리스는 아래와 같은 5가지 조각으로 이루어져 있다.
정수로 이루어진 N×N 표가 주어진다. 테트리스 블록 중 하나를 표에 놓아 블록 아래에 있는 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.
모든 테트리스 블록은 90도씩 회전시킬 수 있다. 일부 조각은 총 4가지 형태를 가질 수 있다. 블록이 모두 표 안에 들어있는 형태는 모두 가능한 형태이다.
예를 들어, 가장 왼쪽 블록을 첫 행에 놓으면 합 80을 얻을 수 있다. 90도 회전시켜 셋째 열에 놓으면 91을 얻을 수 있다.
표의 크기가 4 ×4인 경우에 블록을 놓는 방법의 수는 총 77가지이다. 위의 예제에서 가장 큰 합은 120이다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다.
입력의 마지막 줄에는 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
|
#include<iostream>
#include <algorithm>
using namespace std;
int arr[100][100];
int ans, n, t = 1;
int move[13][4][2] = {
{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
{{0, 0}, {1, 0}, {2, 0}, {3, 0}},
{{0, 0}, {0, 1}, {1, 1}, {1, 2}},
{{0, 1}, {1, 0}, {1, 1}, {2, 0}},
{{0, 0}, {0, 1}, {0, 2}, {1, 2}},
{{0, 0}, {0, 1}, {1, 0}, {2, 0}},
{{0, 0}, {1, 0}, {1, 1}, {1, 2}},
{{0, 1}, {1, 1}, {2, 1}, {2, 0}},
{{0, 0}, {0, 1}, {1, 0}, {1, 1}},
{{0, 0}, {1, 0}, {1, 1}, {2, 0}},
{{0, 1}, {1, 0}, {1, 1}, {2, 1}},
{{0, 1}, {1, 0}, {1, 1}, {1, 2}},
{{0, 0}, {0, 1}, {0, 2}, {1, 1}}
};
int r[4], c[4];
void check(int row, int col) {
bool error;
for (int i = 0; i < 13; i++) {
error = false;
for (int j = 0; j < 4; j++) {
r[j] = row + ::move[i][j][0], c[j] = col + ::move[i][j][1];
if (r[j] < 0 || r[j] >= n || c[j] < 0 || c[j] >= n)
error = true;
}
if (!error) {
int sum = 0;
for (int j = 0; j < 4; j++)
sum += arr[r[j]][c[j]];
ans = max(ans, sum);
}
}
}
int main() {
while (true) {
cin >> n;
if (n == 0)break;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> arr[i][j];
ans = -987654321;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
check(i, j);
cout << t++ << ". " << ans << '\n';
}
return 0;
}
|
cs |
테트로미노 문제처럼 DFS를 이용해서 풀어보려고 했다가 큰 코 다친 문제다.
도형을 회전시키는 것만 가능하기 때문에 DFS로 풀면 안되고 그냥 점의 위치를 지정해서 해결했다.
또 습관처럼 ans를 0으로 초기화했는데 배열에 음수도 있기 때문에 적당한 음수로 처리해줘야 한다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 11687 팩토리얼 0의 개수 (0) | 2020.12.27 |
|---|---|
| 백준 온라인 저지 16508 전공책 (1) | 2020.12.24 |
| 백준 온라인 저지 1038 감소하는 수 (0) | 2020.12.09 |
| 백준 온라인 저지 5958 Space Exploration (0) | 2020.12.07 |
| 백준 온라인 저지 2676 라스칼 삼각형 (0) | 2020.12.07 |
