[코드트리] 금 채굴하기

문제링크

문제 설명

n * n에 금이 있는데 금이 있는 부분은 1 없는 부분은 0으로 주어진다
금의 가격은 개당 m이고,
채굴 비용은 k^2 + (k + 1)^2이다.
마름모 모양으로 채굴할 수 있으며, 마름모 부분이 채굴장 밖을 벗어나도 채굴은 할 수 있으나 금은 없다.

문제 풀이 중 직면한 어려움

• 마름모를 어떻게 구현할 것인가

문제 풀이

• 좌표 내에서 기준 점에서 위치가 k만큼 떨어져 있는지 확인하여
  마름모 부분을 확인

public static int find(int i, int j, int K){
        int cnt = 0;

        for (int dx = -K; dx <= K; dx++) {
            for (int dy = -(K - Math.abs(dx)); dy <= (K - Math.abs(dx)); dy++) {
                int nx = i + dx;
                int ny = j + dy;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 범위 체크
                // (nx, ny)는 K 크기의 마름모 내부에 포함됨
                if (lst[nx][ny] == 1)
                    cnt++;
            }
        }

전체 코드

import java.util.*;

public class Main {
    public static int n;
    public static int[][] lst;

    public static int find(int i, int j, int K){
        int cnt = 0;

        for (int dx = -K; dx <= K; dx++) {
            for (int dy = -(K - Math.abs(dx)); dy <= (K - Math.abs(dx)); dy++) {
                int nx = i + dx;
                int ny = j + dy;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 범위 체크
                // (nx, ny)는 K 크기의 마름모 내부에 포함됨
                if (lst[nx][ny] == 1)
                    cnt++;
            }
        }

        return cnt;
    }

    public static int diff(int cnt, int k, int m){
        int dig = k * k + (k + 1) * (k + 1);
        int gold = cnt * m;

        if (gold - dig < 0)
            return 0;
        return gold - dig;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int m = sc.nextInt(); // 금 가격

        lst = new int[n][n];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++)
                lst[i][j] = sc.nextInt();
        }

        int max_charge = 0;
        //채굴 금액 : k^2 + (k+1)^2
        int k_max = (n + 1) / 2;

        for (int i = 0; i < n; i++) {         // 중심점 i
            for (int j = 0; j < n; j++) {     // 중심점 j
                for (int K = 0; K <= n; K++) { // 마름모 크기
                    int goldCount = find(i, j, K);
                    int cost = K*K + (K+1)*(K+1);

                    if (goldCount * m >= cost) { // 수익이 나는 경우
                        max_charge = Math.max(goldCount, max_charge);
                    }
                }
            }
        }

        System.out.print(max_charge);

    }
}