[코드트리 파이썬] 금 채굴하기

 

문제



손해를 보지 않으면서 채굴할 수 있는 가장 많은 금의 개수를 출력하는 문제이다.

---

풀이

해당 문제에서 마름모의 모양을 결정할 때 중심으로부터 K만큼까지 떨어질 수 있는 것을 정의로 한다.

K = 1

K = 2

 

이 때 마름모의 중앙과 K가 주어졌을 때 임의의 좌표가 마름모 내부에 있는지 확인하는 코드는 다음과 같다.

def getNumOfGold(row, col, k):
    return sum([
        matrix[i][j]
        for i in range(n)
        for j in range(n)
        if abs(row - i) + abs(col - j) <= k
    ])

 

 

 

 

for row in range(n):
    for col in range(n):
        for k in range(2 * (n - 1) + 1):
            numOfGold = getNumOfGold(row, col, k)

따라서 배열을 순회하며 각 위치와 k값에 대해 얻을 수 있는 금의 최대 개수를 알 수 있다.

 

 

if numOfGold * m >= getArea(k):
	maxGold = max(maxGold, numOfGold)

이 후 금을 얻었을 때 손해인지 계산한 후 기존 maxGold와 비교하면 된다.

 

이 때 getArea는 마름모의 넓이를 구하는 함수이며 다음과 같다.

def getArea(k):
    return k * k + (k + 1) * (k + 1)

코드

n, m = map(int, input().split())


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

def getArea(k):
    return k * k + (k + 1) * (k + 1)

def getNumOfGold(row, col, k):
    return sum([
        matrix[i][j]
        for i in range(n)
        for j in range(n)
        if abs(row - i) + abs(col - j) <= k
    ])

maxGold = 0

for row in range(n):
    for col in range(n):
        for k in range(2 * (n - 1) + 1):
            numOfGold = getNumOfGold(row, col, k)

            if numOfGold * m >= getArea(k):
                maxGold = max(maxGold, numOfGold)

print(maxGold)