[백준/파이썬] 14500번 테트로미노

solved.ac Class 3레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/14500

14500번: 테트로미노

문제 해석

그림에서 주어진 블럭의 합이 최대가 되는 수를 구하는 문제이다.

이때 블록은 회전이 가능하므로 해당 경우까지 생각해서 문제를 해결해 주어야 한다.

문제 풀이

모든 경우의 수를 구해주었다. 3가지 방향으로 나누어서 구해주었다.

1. 먼저 누워있는 ㅁㅁㅁㅁ 형태의 도형의 최댓값
2. ㅁㅁㅁ
   ㅁㅁㅁ 다음과 같은 2 * 3 형태의 도형의 최댓값
3. ㅁㅁ
   ㅁㅁ
   ㅁㅁ 다음과 같은 3 * 2 형태의 도형의 최댓값

2, 3번의 형태로 만들어 준 뒤 회전에서 나올 수 있는 형태의 도형에서 빈 도형의 값들을 빼 주어 계산해 주었다.

문제 코드

def check_two_three(blocks):
    sum_score = sum(blocks)
    score = 0
    score = max(score, sum_score - blocks[0] - blocks[1])
    score = max(score, sum_score - blocks[1] - blocks[2])
    score = max(score, sum_score - blocks[3] - blocks[4])
    score = max(score, sum_score - blocks[4] - blocks[5])

    score = max(score, sum_score - blocks[0] - blocks[2])
    score = max(score, sum_score - blocks[3] - blocks[5])

    score = max(score, sum_score - blocks[0] - blocks[5])
    score = max(score, sum_score - blocks[3] - blocks[2])

    score = max(score, sum_score - blocks[0] - blocks[3])
    score = max(score, sum_score - blocks[2] - blocks[5])
    return score

def check_three_two(blocks):
    sum_score = sum(blocks)
    score = 0
    score = max(score, sum_score - blocks[0] - blocks[2])
    score = max(score, sum_score - blocks[2] - blocks[4])
    score = max(score, sum_score - blocks[1] - blocks[3])
    score = max(score, sum_score - blocks[3] - blocks[5])

    score = max(score, sum_score - blocks[0] - blocks[4])
    score = max(score, sum_score - blocks[1] - blocks[5])

    score = max(score, sum_score - blocks[0] - blocks[5])
    score = max(score, sum_score - blocks[1] - blocks[4])

    score = max(score, sum_score - blocks[0] - blocks[1])
    score = max(score, sum_score - blocks[4] - blocks[5])
    return score

def check_four(n, m, arr):
    score = 0
    for i in range(n):
        for j in range(m - 3):
            cur_score = 0
            for k in range(4):
                cur_score += arr[i][j + k]
            score = max(score, cur_score)
    
    for i in range(n - 3):
        for j in range(m):
            cur_score = 0
            for k in range(4):
                cur_score += arr[i + k][j]
            score = max(score, cur_score)
            
    return score

def solve(n, m, arr):
    answer = check_four(n, m, arr)
    
    for i in range(n - 1):
        for j in range(m - 2):
            temp = arr[i][j:j + 3] + arr[i + 1][j: j + 3]
            answer = max(answer, check_two_three(temp))

    for i in range(n - 2):
        for j in range(m - 1):
            temp = arr[i][j:j + 2] + arr[i + 1][j:j + 2] + arr[i + 2][j:j + 2]
            answer = max(answer, check_three_two(temp))

    return answer

n, m = map(int, input().split())
arr = [(list(map(int, input().split()))) for _ in range(n)]

print(solve(n, m, arr))

제출 결과