[코드트리 조별과제] 금 채굴하기

📌 Intermediate Low > Simulation > 격자 안에서 완전탐색 > 금 채굴하기

https://www.codetree.ai/missions/2/problems/gold-mining?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

마름모 모양으로 금을 채굴 -> 손해를 보지 않는 금 개수의 최댓값 구하기

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

def get_gold(r, c, k):
    cnt = 0
    profit = -(k*k + (k+1)*(k+1))

    for i in range(n):
        for j in range(n):
            # (r, c) 좌표에서 반경 k 이내에 있는 좌표 (i, j)
            if abs(r-i) + abs(c-j) <= k:
                cnt += map[i][j]

    profit += cnt * m
    
    # 이익이 0 이상일 때 금의 개수를 구해 리턴하는 함수
    # 이익이 음수면 그냥 0을 리턴
    return cnt if profit >= 0 else 0

ans = 0
for r in range(n):
    for c in range(n):
        for k in range(2 * n):
            cnt = get_gold(r, c, k)

            if cnt > ans:
                ans = cnt

print(ans)