[코드트리/INTERMEDIATE LOW] 금 채굴하기 (JAVA)

📖 문제

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

 

💡  풀이 방식

• 시뮬레이션

완전탐색을 통해  모든 점에 대해 K를 변경하며 채굴할 수 있는 금의 갯수를 센다. 이 때, (금 1개 가격 * 채굴한 금 개수)이 채굴에 드는 비용보다 같거나 큰 경우에만 금의 갯수를 더 큰 값으로 비교해 갱신한다.

 

 

💥 유의사항

k의 범위!

격자 내 모든 격자를 덮기 위한 가능한 K의 최대범위

= 가장 거리가 먼 두 점 (좌측 상단-우측 하단) 거리 계산

: 2 * (N-1)

 

+ 대각선 길이는 가로나 세로 길이의 2배이므로 2*(N-1)이면 충분히 모든 칸 커버 가능

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, m;
    static int[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());   // 금 1개 가격
 
        map = new int[n][n];
        for(int i = 0 ; i < n ; i++) {
            String[] str = br.readLine().split(" ");
            for(int j = 0 ; j < n ; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }
 
        int max = 0; // 손해보지 않으면서 채굴 가능한 최대 금 개수
 
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                for(int k = 0 ; k <= 2 * (n-1) ; k++) {    // 🔔 좌측 상단에서 우측 하단까지 커버하기 위함
                    int goldCnt = countGold(i,j,k);
 
                    if(goldCnt * m >= digCost(k)) {     // 손해보지 않을 때 갱신
                        max = Math.max(max, goldCnt);
                    }
                }                    
            }
        }
 
        System.out.println(max);
    }
 
    private static int countGold(int x, int y, int k) {
        int cnt = 0;
 
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(Math.abs(x - i) + Math.abs(y - j) <= k) {     // 🔔 마름모 모양 (맨해튼 거리)
                    cnt += map[i][j];
                }
            }
        }
 
        return cnt;
    }
 
    // 채굴 비용 계산 메소드
    private static int digCost(int k) {
        return k * k + (k + 1) * (k + 1);
    }
}

 

 

 

---

💦 어려웠던 점

마름모 길이 k 활용하는 부분 (맨해튼 거리)

- 마름모 길이 k를 반복문의 맨 바깥쪽에 두었었다.

- 마름모 길이 k의 범위를 0부터 n까지 했었다. → 2 * (N-1) 이어야 한다.

 

 

🧐 새로 알게 된 내용

특정 위치가 마름모에 포함되었는지 확인하는 방법

마름모 중앙의 위치를 (x,y), 임의 위치를 (i,j)라 할 때 

(중심점과 x거리의 차이 + 중심점과 y거리의 차이) <= K 여야 한다.

|i - x| + |j - y| <= K

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리

✔ 서치하다 보니 SWEA 2117 홈 방범 서비스와 비슷하다.