[알고리즘] 코드트리 알고리즘 입문 - 트로미노

트로미노

https://www.codetree.ai/missions/2/problems/tromino/description

내 풀이

n, m = tuple(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(n)]
seq = [0 for _ in range(3)]

def max_seq():
    result = 0
    for i in seq:
        result += i
    # print('result')
    # print(result)
    return result

def max_apple(row, col):
    square, min_cell = 0, float('inf')
    for i in range(row, row+2):
        for j in range(col, col+2):
            min_cell = min(min_cell, grid[i][j])
            square += grid[i][j]
    # print('min_cell')
    # print(min_cell)
    return square - min_cell

max_sum = 0

# stick
for row in range(n):
    for col in range(m):
        if col + 2 >= m:
            continue
        seq = grid[row][col:col+3]
        max_sum = max(max_sum, max_seq())
# print('가로 끝')
for col in range(m):
    for row in range(n):
        if row + 2 >= n:
            continue
        # print(f'row: {row}')
        for i in range(row, row+3):
            seq.pop()
            seq.insert(0,grid[i][col])
        # print(f'seq: {seq}')
        max_sum = max(max_sum, max_seq())
# print('세로 끝')
# apple
for row in range(n):
    for col in range(m):
        if row + 1 >= n or col + 1 >= m:
            continue
        max_sum = max(max_sum, max_apple(row, col))

print(max_sum)

이번 문제는 한 번에 통과해서 기분이 좋다.

도형이 2가지인데 3칸이라는 공통점이 있어서 함수를 하나만 만들어서 돌려쓰고 싶었지만, 왼쪽 의자같이 생긴 도형을 grid에서 추출하는데

• 2x2 행렬에서 각 모서리마다 하나씩 제외하여 3칸 행을 만드는 것보다
• 4칸의 총합에서 4칸 중 가장 작은 수를 구해 총합에서 가장 작은 수를 빼주는 작업이 더 구현하기 쉬울 것 같아

이 방향으로 선회하여 풀었다.

중간에 세로 열 최대값을 계산할 때 seq.pop()과 seq.insert(0, grid[i][col])은 seq 리스트의 index(0, 1, 2 고정)와 세로 열 index(0, 1, 2 또는 1, 2, 3)와 일치하지 않아 seq[i] = grid[i][col] 대신 직접 빼고 넣어주게 됐다(deque 자료형을 사용하면 될 것 같지만 숙련도 이슈로 사용하지 못했다).

---

그나저나 스터디 이틀 남았는데 문제는 10개 남았다 ㅋ 내 실력 진짜 알고리즘계 거북이인듯 ..