[코드트리 챌린지] 2주차 - 금 채굴하기

· 문제링크

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

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

· 핵심

1. 시간복잡도 : O(N*N*(2(N-1))^2 + (2(N-1)+1)^2) = O(N^4)

→ K의 최대값 : 2(N - 1) → 최대로 살펴봐야할 마름모 격자의 수 : (2(N-1))^2 + (2(N-1)+1)^2

2. 마름모 : 택시기하학에서의 원으로 비유할 수 있으며 즉 격자 내에서 같은 거리의 모임

→ 좌표(0, 0)기준으로 K에 따른 마름모의 껍데기 좌표를 delta에 모두 기록

→ 기준 좌표가 변경된 경우 평행이동

→ (x,  k - x) - 제 1사분면 / (x,  x - k) - 제 2사분면 / (-x, x - k) - 제 3사분면 / (-x, k - x) - 제 4사분면 

def taxi_circle(k):
    if k == 0:
        return [(0, 0)]
    points = [] # (x, y)
    points.append((k, 0))
    points.append((-k, 0))
    for x in range(k):
        points.append((x, k - x)) # (0, k), (1, k-1) ...
        points.append((x, x - k)) # (0, -k), (1, 1 - k)
    for x in range(1, k):
        points.append((-x, k - x))
        points.append((-x, x - k))
    return points

---

· 코드(Python)

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

delta = []

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

def taxi_circle(k):
    if k == 0:
        return [(0, 0)]
    points = [] # (x, y)
    points.append((k, 0))
    points.append((-k, 0))
    for x in range(k):
        points.append((x, k - x)) # (0, k), (1, k-1) ...
        points.append((x, x - k)) # (0, -k), (1, 1 - k)
    for x in range(1, k):
        points.append((-x, k - x))
        points.append((-x, x - k))
    return points

for k in range(2*(n-1)+1):
    delta.append(taxi_circle(k))

ans = 0

for y in range(n):
    for x in range(n):
        gold_cnt = 0
        for k in range(2*(n-1)+1):
            for dx, dy in delta[k]:
                cx, cy = x + dx, y + dy
                if in_range(cx, cy) and board[cy][cx] == 1:
                    gold_cnt += 1
            if gold_cnt * m >= k * k + (k+1) * (k+1):
                ans = max(ans, gold_cnt)

print(ans)