문제 풀이
구현
map = NxM 크기의 종이에 적힌 정수 값
answer = 테트로미노가 놓인 칸에 쓰여 있는 수들의 합 중 최댓값
| 변수명 | 테트로미노 |
|---|---|
| box |  |
| longVertical |  |
| longHorizontal |  |
| tVertical1 |  |
| tVertical2 |  |
| sVertical1 |  |
| sVertical2 |  |
| lVertical1 |  |
| lVertical2 |  |
| lVertical3 |  |
| lVertical4 |  |
| tHorizontal1 |  |
| tHorizontal2 |  |
| sHorizontal1 |  |
| sHorizontal2 |  |
| lHorizontal1 |  |
| lHorizontal2 |  |
| lHorizontal3 |  |
| lHorizontal4 |  |
종이의 모든 칸 (i, j)에 대해 해당 칸을 테트로미노 격자의 가장 맨 왼쪽 위칸이라고 했을 때 각 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 구해 최댓값을 answer에 저장하고 출력하면 정답
풀이 설명
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
테트로미노를 회전, 대칭까지 포함해 N x M의 크기로 구분하면 다음과 같이 나누어진다.
- 2 x 2 크기의 테트로미노
- 4 x 1 크기의 테트로미노
- 1 x 4 크기의 테트로미노
- 3 x 2 크기의 테트로미노
| | | |
|---|---|---|---|
| | | |
- 2 x 3 크기의 테트로미노
| | | |
|---|---|---|---|
| | | |
이렇게 구한 모든 테트로미노의 격자 칸 중에서 가장 왼쪽 위칸을 테트로미노의 시작 칸이라고 하면 이를 NxM 크기의 종이의 모든 칸에 대해서 값의 합을 구해 최댓값을 구해 출력하면 정답이 된다.
소스 코드
import java.io.StreamTokenizer
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun nextInt(): Int{
nextToken()
return nval.toInt()
}
val N = nextInt()
val M = nextInt()
val map = Array(N){IntArray(M)}
for(i in 0 until N){
for(j in 0 until M){
map[i][j] = nextInt()
}
}
var answer = 0
for(i in 0 until N ){
for(j in 0 until M){
if(i <= N - 2 && j <= M - 2){
val box = map[i][j] + map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1]
answer = maxOf(answer, box)
}
if(i <= N - 4){
val longVertical = map[i][j] + map[i + 1][j] + map[i + 2][j] + map[i + 3][j]
answer = maxOf(answer, longVertical)
}
if(j <= M - 4){
val longHorizontal = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i][j + 3]
answer = maxOf(answer, longHorizontal)
}
if(i <= N - 3 && j <= M - 2){
val tVertical1 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j]
answer = maxOf(answer, tVertical1)
val tVertical2 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j + 1]
answer = maxOf(answer, tVertical2)
val sVertical1 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j + 1]
answer = maxOf(answer, sVertical1)
val sVertical2 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j]
answer = maxOf(answer, sVertical2)
val lVertical1 = map[i][j] + map[i][j + 1] + map[i + 1][j] + map[i + 2][j]
answer = maxOf(answer, lVertical1)
val lVertical2 = map[i][j] + map[i][j + 1] + map[i + 1][j + 1] + map[i + 2][j + 1]
answer = maxOf(answer, lVertical2)
val lVertical3 = map[i][j] + map[i + 1][j] + map[i + 2][j] + map[i + 2][j + 1]
answer = maxOf(answer, lVertical3)
val lVertical4 = map[i][j + 1] + map[i + 1][j + 1] + map[i + 2][j] + map[i + 2][j + 1]
answer = maxOf(answer, lVertical4)
}
if(i <= N - 2 && j <= M - 3){
val tHorizontal1 = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j + 1]
answer = maxOf(answer, tHorizontal1)
val tHorizontal2 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2]
answer = maxOf(answer, tHorizontal2)
val sHorizontal1 = map[i][j] + map[i][j + 1] + map[i + 1][j + 1] + map[i + 1][j + 2]
answer = maxOf(answer, sHorizontal1)
val sHorizontal2 = map[i][j + 1] + map[i][j + 2] + map[i + 1][j] + map[i + 1][j + 1]
answer = maxOf(answer, sHorizontal2)
val lHorizontal1 = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j]
answer = maxOf(answer, lHorizontal1)
val lHorizontal2 = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j + 2]
answer = maxOf(answer, lHorizontal2)
val lHorizontal3 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2]
answer = maxOf(answer, lHorizontal3)
val lHorizontal4 = map[i][j + 2] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2]
answer = maxOf(answer, lHorizontal4)
}
}
}
println(answer)
}