백준 2140, 28303, 2258

백준 2140 지뢰찾기  💣 

https://www.acmicpc.net/problem/2140

2140번: 지뢰찾기

 

💣 테두리에 인접한 영역만 직접 계산하고, 나머지 가운데 영역들은 모두 지뢰가 있다고 가정해서 지뢰의 최대 개수를 계산한다. 

💣 그리디, 구현 문제로 분류되어 있다. 아래 그림의 분홍 형광펜 영역 기준 8방향을 탐색하는 Around함수, 그리고 Around 결과 따라 count를 감소시킬지 / 주변 숫자를 1씩 감소시킬지를 결정한다.

💣 나머진 아래 그림 참고 

💣 코드

import java.io.*;
public class p2140 {
    private static int[][] map;
    private static int[] dirX = { 0, -1, -1, -1, 0, 1, 1, 1};
    private static int[] dirY = { -1, -1, 0, 1, 1, 1, 0, -1};
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        if (n <= 2) {
            System.out.println(0);
            return;
        }
        map = new int[n][n];
        int count = (n-2)*(n-2);


        for(int i = 0; i < n; i++) {
            String temp = br.readLine();
            String[] split = temp.split("");
            for (int j = 0; j < n; j++) {
                if (split[j].equals("#")) {
                    map[i][j] = Integer.MIN_VALUE;
                } else {
                    map[i][j] = Integer.parseInt(split[j]);
                }
            }
        }


        for (int i = 1; i < n-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (i == 1 || i == n-2 || j == 1 || j == n-2) {
                    if (Around(i, j)) {
                        Delete(i, j);
                    } else { // 주변에 0이 있다는 뜻이니 무조건 그 칸은 지뢰후보 제외
                        count--;
                    }
                }
            }
        }
        System.out.println(count);

    }

    private static void Delete(int x, int y) {
        for (int i = 0; i < 8; i++) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            if (map[nextX][nextY] >= 0) {
                map[nextX][nextY]--;
            }

        }
    }
    private static boolean Around(int x, int y) {

        for (int i = 0; i < 8; i++) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            if (map[nextX][nextY] == 0) {
                return false;
            }

        }
        return true;
    }

    private static boolean isValid (int x, int y) {
        if (x < 0 || x > n-1 || y < 0 || y > n-1) {
            return false;
        }
        return true;
    }
}

 

 

---

 

백준 28303 자석 🧲

 

https://www.acmicpc.net/problem/28303

28303번: 자석

🧲 누적합 문제이다.... 무지성으로 풀다가 메모리 초과와 시간 초과를 번갈아 만날 수 있는 문제... 거의 안 풀어본 문제 유형이었는데 출처를 보니 알고리즘 대회문제였다. 동적 계획법으로 시작해서 누적합으로 끝난... 

🧲 문제에서 주어진 공식을 일반화 해서 식을 세운다. 

En - Es - (N index - S index) * K
= En - Es - (N index * K - S index * K)
= En - Es - N index * K + S index * K
= (En - N index * K) - (Es - S index * K)

 

🧲 에너지를 최대로 만들 수 있는 값을 계산하면 된다. (여기서 착각한게, 절대값의 최대를 계산하는게 아니다. -건 +건 다양한 변화량들 중 가장 큰 값을 찾는 문제이다. ) 이 에너지에는 아래와 같은 요소가 영향을 미친다. 

• N극 에너지는 최대한 크게
• S극 에너지는 최대한 작게
• N극과 S극의 인덱스 차이 작게 (자석 길이 짧게)

따라서, 위 공식에서 En - N index * K 는 최대한 크게, Es - S index * K는 최대한 작게 만들어야 한다. 

Es - S index * K = left 로 정의하고 문제를 풀었다. 

 

🧲 풀이과정 첨부 

 

🧲 for문 2중으로 돌리면 시간초과가 난다. 그러므로 for 문 하나에 해결해나가는게 키 포인트

• index 가 1부터 시작하는데, 얘는 N극과 S극의 인덱스 차이와 같다.
• index를 이동하면서 에너지 총량을 Max로 갱신하는 작업 +  left는 위에서 설명했듯 최소로 만들어줘야 하므로 left를 Min으로 갱신하는 작업이 필요하다. 
• 그리고 N-S 뒤집을 수도 있다. 그냥 편하게 reverse 배열에 에너지 반대로 넣은 다음 동일 로직으로 계산했다. 이정도는 메모리 제한에 걸리지 않았다.

 

🧲 전체 코드 

import java.io.*;
import java.util.*;
public class p28303 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        long answer = Long.MIN_VALUE;
        long[] num = new long[n];
        long[] reverse = new long[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Long.parseLong(st.nextToken());
            reverse[n-i-1] = num[i];
        }


        long left = num[0];
        for (int index = 1; index < n; index++) {
            // left가 S극을 의미, 가장 작아야만 에너지가 제일 크게 나옴
            answer = Math.max(answer, num[index] - ((long) index * k) - left);
            left = Math.min(left, num[index] - ((long) index * k));
        }

        left = reverse[0];
        for (int index = 1; index < n; index++) {
            answer = Math.max(answer, reverse[index] - ((long) index * k) - left);
            left = Math.min(left, reverse[index] - ((long) index * k));
        }

        System.out.println(answer);
    }
}

 

 

 

---

백준 2258 정육점 🥩

 

https://www.acmicpc.net/problem/2258

2258번: 정육점

 

🥩 Greedy, "가격은 적게, 양은 많게"가 이 문제가 요구하는 욕심(?)이다. 이를 기준으로 🥩를 우선순위큐에 넣기

🥩 주의사항 : 이 문제에서 가격은 같은데 양이 다른 고기가 있을 수도 있다.

• 예를 들어 가격이 2인 고기가 양이 2, 3, 4인 채로 포장되어있다 하자.
• 가격이 2이고 양이 4로 가장 많은 고기를 산다.
• 그치만 양이 2, 3인 애들은 가격이 더 적은게 아니기 때문에 담을 수 없다. 
• 2,3인 애들을 가져가려면 각각 가격만큼 추가로 지불해야한다. 이 조건을 빼먹지 말자. 

🥩 각 경우마다 총 지불할 금액, 고기총량, 고기들 중 최대 가격을 계산해주면 된다. 

🥩 고기 총량이 필요한 양을 넘긴 시점부터 Math.min으로 갱신해주면 된다. 

 

🥩 추가 설명 : 여기 있는 예제는 문제 예제 말고 일부러 같은 가격에 양 다른 고기를 넣어봤다. 

 

🥩 전체 코드

import java.io.*;
import java.util.*;
public class p2258 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int need = Integer.parseInt(st.nextToken());
        int money = 0; // 사용 금액
        int maxMoney = 0;
        int amount = 0;
        int answer = Integer.MAX_VALUE;
        boolean isSuccess = false;

        PriorityQueue<Meat> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            pq.add(new Meat(size, price));
        }

        while (!pq.isEmpty()) {
            Meat poll = pq.poll();
            if (maxMoney < poll.price) {
                maxMoney = poll.price;
                money = poll.price;
            } else if (maxMoney == poll.price) {
                money += poll.price;
            }
            amount += poll.size;
            if (amount >= need) {
                answer = Math.min(answer, money);
                isSuccess = true;
            }
        }

        if (isSuccess) {
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }

    }

    private static class Meat implements Comparable<Meat> {
        int size;
        int price;

        Meat(int size, int price) {
            this.size = size;
            this.price = price;
        }

        @Override
        public int compareTo(Meat o) {
            if (this.price == o.price) {
                return o.size - this.size;
            }
            return this.price - o.price;
        }
    }
}