백준 17070, 2212, 12018, 14719

백준 17070

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

17070번: 파이프 옮기기 1

- BFS로도 풀어보고, DP로도 풀어봤다. 처음에 BFS풀 때 움직일 수 있는 모든 방향을 리스트에 저장해서 다 도는 방식으로 구현했었는데, 시간초과 났었다. 
- 오른쪽으로 이동 가능한 경우 : 이전이 대각선이거나 가로 방향일 때
- 아래로 이동 가능한 경우 : 이전이 대각선이거나 세로 방향일 때
- 대각선으로 이동 가능한 경우 : 이전 상태 상관없이 다 가능
 
이렇게 3가지 케이스로 나눠서 풀어야 한다. 

import java.util.*;
import java.io.*;
public class p17070_BFS {
    private static int n, answer = 0;
    private static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];


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

        BFS(new Pos(0, 1, 0));

        System.out.println(answer);
    }

    public static void BFS(Pos pos) {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(pos);

        while (!queue.isEmpty()) {
            Pos poll = queue.poll();
            if (poll.x == n-1 && poll.y == n-1) {
                answer++;
                continue;
            }

            // 오른쪽으로 이동 가능한 경우 : 현 파이프 상태가 가로거나 대각선일 때
            if (poll.dir == 0 || poll.dir == 2) {
                if (isValid(poll.x, poll.y + 1)) {
                    queue.add(new Pos(poll.x, poll.y+1, 0));
                }
            }
            // 아래쪽으로 이동 가능한 경우 : 현 파이프 상태가 세로거나 대각선일 때
            if (poll.dir == 1 || poll.dir == 2) {
                if (isValid(poll.x + 1, poll.y)) {
                    queue.add(new Pos(poll.x+1, poll.y, 1));
                }

            }

            // 이전의 상태가 어떻든 대각선 방향은 모두 이동 가능
            if (isValid(poll.x + 1, poll.y + 1) && checkAround(poll.x + 1, poll.y + 1)) {
                queue.add(new Pos(poll.x+1, poll.y + 1, 2));
            }

        }
    }
    public static boolean checkAround (int nextX, int nextY) {
        return map[nextX-1][nextY] == 0
                && map[nextX][nextY-1] == 0
                && map[nextX][nextY] == 0;
    }

    public static boolean isValid(int nextX, int nextY) {
        return nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && map[nextX][nextY] == 0;
    }
    public static class Pos {
        int x;
        int y;
        int dir;

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

참고로 위 케이스 3개 생각해보면 DP로 푸는게 훨씬 간단하다는 것을 알 수 있다.. 
DP 배열을 방향까지 저장하기 위해 int[n][n][3] 크기의 3차원 배열로 만들면 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p17070_DP {
    private static int n;
    private static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int[][][] DP = new int[n][n][3];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        DP[0][1][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 2; j < n; j++) {
                if (map[i][j] == 0) {
                    // 해당 좌표에 가로로 오는 법
                    DP[i][j][0] = DP[i][j-1][0] + DP[i][j-1][2];
                    // 세로로 오는 법
                    if (i >= 1) {
                        DP[i][j][1] = DP[i-1][j][1] + DP[i-1][j][2];
                        // 대각선으로 오는 법
                        if (map[i-1][j] == 0 && map[i][j-1] == 0) {
                            DP[i][j][2] = DP[i-1][j-1][0] + DP[i-1][j-1][1] + DP[i-1][j-1][2];
                        }
                    }
                }
            }
        }

        System.out.println(DP[n-1][n-1][0] + DP[n-1][n-1][1] + DP[n-1][n-1][2]);
    }
}

---

백준 2212

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

2212번: 센서

그리디 알고리즘
수학적인(?) 생각이 좀 필요했다.

6
2
1 6 9 3 6 7

일단 각 센서 위치를 오름차순으로 정렬한 후, 각 센서별로 이웃하는 센서와의 거리차이를 기록한다. 
센서 위치 : 1 3 6 6 7 9
각 센서 간 차이 : 2 3 0 1 2 => 3 2 2 1 0 (내림차순)
그리고 이 센서간 차이들 중 가장 큰것부터 (센서 개수 - 1 )만큼 제거하면 된다. 그림이 좀 더 이해가 쉽다.

 
 

import java.util.*;
import java.io.*;
public class p2212 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int spot = Integer.parseInt(br.readLine());
        int answer = 0;
        ArrayList<Integer> dif = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] sensor = new int[n];
        for (int i = 0; i < n; i++) {
            sensor[i] = Integer.parseInt(st.nextToken());
        }
        if (spot > n) {
            System.out.println(answer);
            return;
        }
        Arrays.sort(sensor);
        for (int i = 1; i < n; i++) {
            dif.add(sensor[i] - sensor[i-1]);
        }
        Collections.sort(dif, Collections.reverseOrder());
        for (int i = spot-1; i < dif.size(); i++) {
            answer += dif.get(i);
        }
        System.out.println(answer);
    }
}

---

 

백준 12018

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

12018번: Yonsei TOTO

- 얘도 그리디인데, 조건 몇 개만 잘 보면 된다. 
- 무조건 주어진 마일리지 한도 내에서 많이 듣는게 목적이니 수강인원이 차지 않은 과목(cur< limit)은 다 넣기. 최소값인 1만 넣으면 된다
- 수강인원보다 더 신청자가 많다면, 내가 딱 수강인원 커트에 들어가도록 마일리지를 사용하면 된다. 제일 낮은 애 마일리지부터 탐색, 4명이 정원인데 6명신청했다 이러면 3번째로 낮은애 마일리지만큼 사용하면 된다.
 

import java.util.*;
import java.io.*;
public class p12018 {
    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 m = Integer.parseInt(st.nextToken());
        int answer = 0;

        PriorityQueue<Integer> spend = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            int limit = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            if (cur < limit) {
                spend.add(1);
            }
            else  {
                PriorityQueue<Integer> temp = new PriorityQueue<>();
                for (int j = 0; j < cur; j++) {
                    temp.add(Integer.parseInt(st.nextToken()));
                }
                if (cur > limit) {
                    for (int j = cur - limit; j > 0; j--) {
                        temp.poll();
                    }
                }
                int min = temp.poll();
                spend.add(min);
               
            }
        }

        while (!spend.isEmpty()) {
            int poll = spend.poll();
            if (m - poll >= 0) {
                answer++;
                m -= poll;
            }
            if (m <= 0) {
                break;
            }
        }

        System.out.println(answer);
    }
}

---

백준 14719
https://www.acmicpc.net/problem/14719

14719번: 빗물

- 찾으려는 index 기준으로 왼쪽, 오른쪽 탐색한다.
- 왼쪽의 max, 오른쪽의 max 비교 후 둘 중 더 작은 값에서 index의 높이를 빼준 것이 고이는 빗물 양

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p14719 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int height = Integer.parseInt(st.nextToken());
        int width = Integer.parseInt(st.nextToken());

        ArrayList<Integer> temp = new ArrayList<>();
        int[] wall = new int[width];

        int answer = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < width; i++) {
            wall[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < width - 1; i++) {

            // left part
            int[] left = Arrays.copyOfRange(wall, 0, i+1);
            Arrays.sort(left);

            // right part
            int[] right = Arrays.copyOfRange(wall, i+1, width);
            Arrays.sort(right);

            if (wall[i] < right[right.length-1] && wall[i] < left[left.length-1]) {
                answer += (Math.min(right[right.length-1], left[left.length-1]) - wall[i]);
            }
        }

        System.out.println(answer);
    }
}