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

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

🗒️알고리즘 분류

#완전 탐색 #brute force

📌기억해야 할 포인트

우선 N 의 범위가 최대 20, M 의 범위가 최대 10 이기 때문에, 완전 탐색 알고리즘으로 풀어야 한다는 것을 깨달았다.

하지만, 처음에 정사각형의 크기에 따른 마름모의 크기를 직접 코드로 구현해주다가 시간을 엉뚱한데 다 썼다.

마름모를 구할 때 나름의 규칙이 있었기 때문에 그것을 만족하도록 다 구현해주었는데, 결국은 문제를 틀렸고 방법은 따로 있었다.

• 결국 마름모의 범위만을 구하면 되기 때문에, 임의의 점 (i,j) 에 대하여 Math.abs(i-x) + Math.abs(j-y) <= k 을 만족하기만 하면 된다.
• 괜히 직접 마름모 칸을 전부 탐색하는 코드를 구현했다..

📝풀이 코드(JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 0; j < n; j++) {
                if (st.hasMoreTokens()) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
        }

        br.close(); 

        int answer = 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 goldCount = getGoldCount(arr,i,j,k);
                    int goldMoney = goldCount * m;

                    if(goldMoney >= getMineCost(k)) {
                        answer = Math.max(answer, goldCount);
                    }
                }
            }
        }
        
        System.out.println(answer);
        return;
    }

    private static int getGoldCount(int[][] arr, int x, int y, int k) {
        int goldCount = 0;

        for (int i=0; i< arr.length; i++) {
            for (int j=0; j< arr[i].length; j++) {
                if (Math.abs(i-x) + Math.abs(j-y) <= k) { 
                    goldCount += arr[i][j];
                }
            }
        }
        return goldCount;
    }
    
    private static int getMineCost(int k) {
        return (k*k) + (k+1)*(k+1);
    }
}

⏰총 풀이시간

• 180분;;