[Code Tree][Python] IL Simulation 금 채굴하기

Overview

• 체감 난이도: ★★★☆☆
• 문제 레벨: IL / Simulation / 격자 안에서 완전 탐색 / 연습 문제
• 문제 유형: Simulation
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

Trail 4 / Chapter 1 / Lesson 1 / 연습 문제

https://www.codetree.ai/trails/complete/curated-cards/challenge-gold-mining/description

Code Tree | Learning to Code with Confidence

 

[코드]

문제 설명:

• 마름모 모양을 유지한다면, 격자를 벗어나는 크기의 마름모도 가능하다. 
• 채굴에 드는 비용은 마름모 안의 격자 개수만큼 들어간다. K * K + (K + 1) * (K + 1) 
• 금 한 개의 가격이 m일 때, 손해를 보지 않으면서 채굴할 수 있는 가장 많은 금의 개수를 출력해라. 

문제 조건:

1. 금은 격자 안에만 존재한다. 
2. 마름모 모양이여야 한다. (마름모의 크기는 제한 x)
3. 마름모는 격자를 벗어날 수 있되, (마름모 내 금의 개수 * 금의 가격 >= 채굴 비용) 만족해야 한다. 

결론은,

마름모 크기를 키워가며, 손해를 보지 않는 선에서 가장 많은 금의 개수를 구하라 인데

 

내가 구현한 방법은, 

main

• K를 증가시키며 탐색한다. 
• 각 K에 대해 모든 격자점 (i, j)을 중심으로 검사한다. 
• 수익 계산 = m * gold - (K * K + (K + 1) * (K + 1))
• 수익이 0 이상일 때 최대 금 개수 갱신
• 비용이 전체 금의 가치보다 커지면 종료한다. (격자 전체에 금이 있다고 가정할 때 최댓값 설정)

chk(x, y, K)

• 주어진 중심점 (x, y)에서 k 크기의 마름모 영역 내 금의 개수를 계산한다. 
• 이중 반복문으로 마름모 모양을 탐색한다. 
• k-abs(i)로 각 행에서의 열 범위를 조절한다. 
• 금 유무는 격자 범위 내에서만 확인한다. (인덱스 범위 초과 에러 방지)

 

 

마름모 범위 (구체적인 설명)

# 마름모 영역 전체 탐색
    for i in range(-k, k + 1):
        # k-|i|: 현재 행에서 탐색해야 할 열의 범위
        for j in range(-(k - abs(i)), k - abs(i) + 1):
            nx, ny = x + i, y + j
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                cnt += 1

i=-2일 때: j는 -(2-|-2|) ~ (2-|-2|) = -(0) ~ 0
  [ ]

i=-1일 때: j는 -(2-|-1|) ~ (2-|-1|) = -(1) ~ 1
  [ ][ ][ ]

i=0일 때: j는 -(2-|0|) ~ (2-|0|) = -2 ~ 2
  [ ][ ][ ][ ][ ]

i=1일 때: j는 -(2-|1|) ~ (2-|1|) = -(1) ~ 1
  [ ][ ][ ]

i=2일 때: j는 -(2-|2|) ~ (2-|2|) = -(0) ~ 0
  [ ]

 

 

[최종 코드]

시간복잡도: O(N²K²)

n, m = map(int, input().split())  # 격자 크기, 금 가격
grid = [list(map(int, input().split())) for _ in range(n)]


# Write your code here!
def chk(x, y, k):
    cnt = 0

    # 마름모 영역 전체 탐색
    for i in range(-k, k + 1):
        # k-|i|: 현재 행에서 탐색해야 할 열의 범위
        for j in range(-(k - abs(i)), k - abs(i) + 1):
            nx, ny = x + i, y + j
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                cnt += 1

    return cnt


# main
K, max_gold = 0, 0

while True:
    cost = K * K + (K + 1) * (K + 1)
    if cost > m * (n * n):
        break

    for i in range(n):
        for j in range(n):
            gold = chk(i, j, K)  # 금 개수 세기
            profit = m * gold - cost

            if profit >= 0:
                max_gold = max(max_gold, gold)

    K += 1

print(max_gold)