[코드트리/INTERMEDIATE LOW] Simulation 금 채굴하기 Python

 

🔥 문제링크

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

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

 

 

🔥 문제

 

 

🔥 풀이

✅ k 크기만큼의 마름모 모양을 탐색하는 방법 : 기준점으로부터 떨어진 거리의 절대값이 k 보다 작은 구역을 모두 탐색

✅ 예시

 

 

🔥 코드

# 금 탐색 함수
def find_out_gold(x, y, k):
    total_gold = 0

    for i in range(n):
        for j in range(n):
            if abs(x-i) + abs(y-j) <= k: # 기준점으로부터 떨어진 거리의 절대값이 k값보다 작은 좌표 모두 탐색
                total_gold += goldMap[i][j]
    
    return total_gold



# 금 채굴 비용 함수
def gold_cost(k): 
    return k**2 + (k+1)**2



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


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


max_gold = 0 # 이익을 볼 수 있는 최대 금 채굴 개수


for i in range(n):
    for j in range(n):
        for k in range(n): # 최대로 키울 수 있는 마름모 지름 : n
        	
            # 좌표 돌면서 채굴한 금의 가치가 금 채굴 비용보다 크고 이전에 탐색한 좌표보다 많은 금을 탐색한 경우
            if (find_out_gold(i, j, k)*m) - gold_cost(k) >= 0 and find_out_gold(i, j, k) > max_gold:
            	
                #최대 금 채굴량 갱신
                max_gold = find_out_gold(i, j, k)

print(max_gold)