백준 15486, 14658

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

15486번: 퇴사 2

 

- 이전에 퇴사 문제(14501, 퇴사1, 실버3) 를 풀었었어서 쉽게 푼 동적계획법 문제

- DP[i] 를 i번째 날부터 퇴사날까지 얻을 수 있는 최대 이익으로 생각하고 배열을 역순으로 계산해나가면 된다. 

- 참고로 퇴사 날부터 거슬러서 계산을 해줘서 일부러 DP배열 사이즈를 한 칸 더 선언해뒀다. 

- 각 상담별로 소요 기간을 보면서 퇴사전에 끝난 경우 / 퇴사 전에 안끝나는 경우 나누고, 퇴사 전에 끝날 경우에도 최대한 많이 벌어야 하므로 비교를 해줘야 한다. 

- 상담에 소요되는 기간이 하루 이하인 경우에는 (사실 1일 이상 소요된다고 조건에 주어져서 ==1로 바꿔도 될 것 같다) 바로 DP[i+1]로 가는게 아니고 그날 당일 상담할 수 있어서 price를 더해준다. 

 

import java.util.Scanner;
public class p15486 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] time = new int[n];
        int[] price = new int[n];
        int[] DP = new int[n+1];

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

        for (int i = n-1; i >= 0; i--) {
            if (i + time[i] <= n) {
                if (time[i] <= 1) {
                    DP[i] = DP[i+1] + price[i];
                } else {
                    DP[i] = Math.max(DP[i+1], DP[i+time[i]] + price[i]);
                }

            } else {
                DP[i] = DP[i+1];
            }
        }

        System.out.println(DP[0]);
    }
}

 

---

 

 

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

14658번: 하늘에서 별똥별이 빗발친다

- 처음엔 각 별을 트램펄린 꼭지점에 놓는 걸 생각했다. 

- 근데 계속 실패하길래 구글링을 해봤는데, 별들이 다이아 형태로 놓여있을 때가 반례가 된다고 한다.

- (4, 4), (6, 2) ,(6, 6) (8, 4)이런식으로 놓여있으면 트램펄린을 (4,2) ~ (8, 6)에 걸치게 두면 4개 다 튕길 수 있는데 처음 방식대로 하면 안된다. 

- 따라서 각 별 좌표의 X, Y 좌표 가지고 조합해서 2중 for문으로 트램펄린의 왼쪽 꼭짓점을 결정하고, 이를 모든 별 대상으로 완탐 돌리면된다. 

- 그리고 튕기지 못한 별똥별 개수를 세는 것이므로 전체 별똥별 개수에서 튕긴 것 빼줘야 한다. 

 

import java.io.*;
import java.util.*;
public class Main {
    static ArrayList<Pos> stars;
    static int size;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int width = Integer.parseInt(st.nextToken());
        int height = Integer.parseInt(st.nextToken());
        size = Integer.parseInt(st.nextToken());
        int num = Integer.parseInt(st.nextToken());
        int answer = Integer.MAX_VALUE;

        stars = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            stars.add(new Pos(x, y));
        }

        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                answer = Math.min(
                        answer,
                        num - countStars(new Pos(stars.get(i).x, stars.get(j).y)));
            }
        }

        System.out.println(answer);
    }

    static int countStars(Pos start) {
        int count = 0;

        for (Pos star : stars) {
            if (star.x >= start.x
                    && star.x <= start.x + size
                    && star.y >= start.y
                    && star.y <= start.y + size) {
                count++;
            }
        }

        return count;
    }


    static class Pos {
        int x;
        int y;

        Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}