[코드트리] 금 채굴하기 Python

마름모 구하는데 4시간 걸렸다,,

자만하지말자,,

마름모가 정사각형을 유지하며 커지지 않는다는 것을 왜 3시간동안 몰랐을까,,

# n, m 입력
n, m = map(int, input().split())
# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# get_cost(s)
def get_cost(s):
    return s * s + (s+1) * (s+1)

# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# get_income(x, y, s)
def get_income(x, y, s):
    
    # curr_income
    curr_income = 0

    # 위쪽
    curr_range = 0
    for i in range(x-s, x):
        for j in range(y - curr_range, y + curr_range + 1):
            if in_range(i,j):
                curr_income += grid[i][j] * m

        # curr_range 1 올려주기
        curr_range += 1
    
    # 가운데
    curr_range = s
    for i in range(y - curr_range, y + curr_range + 1):
        if in_range(x, i):
            curr_income += grid[x][i] * m

    # 아래
    # curr_range
    curr_range = 0
    for i in range(x+s, x, -1):
        for j in range(y - curr_range, y + curr_range + 1):
            if in_range(i, j):
                curr_income += grid[i][j] * m

        # curr_range 1 올려주기
        curr_range += 1
    
    # 반환
    return curr_income

# 설계
# max_gold
max_gold = 0

# 완전 탐색 시작 -> 격자 안
for i in range(n):
    for j in range(n):
        # 완전 탐색 시작 -> 마름모의 크기
        for k in range(2 * n):
            # income, cost
            income, cost = get_income(i, j, k), get_cost(k)

            # income이 cost 이상이면
            if income >= cost:
                
                # max_gold update
                max_gold = max(max_gold, income // m)

# 출력
print(max_gold)