백준 1149, 12852, 17135

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

1149번: RGB거리

동적계획법 문제

- 각 색칠 비용 저장할 2차원 배열 cost

- DP[ i ] [ j ] : i번째 집에  j색(0 빨 - 1 파 - 2 초) 칠했을 때 드는 최소 비용 

- 이웃하는 집끼리 색 안겹치게 하는 것만 기억하면 쉬운 문제 

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

public class p1149 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int answer = Integer.MAX_VALUE;

        int[][] costs = new int[n][3];
        int[][] DP = new int[n][3];

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

        System.arraycopy(costs[0], 0, DP[0], 0, 3);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                DP[i][j] = Math.min(DP[i-1][(j+1)%3] , DP[i-1][(j+2)%3]) + costs[i][j];
            }
        }

        for (int j = 0; j < 3; j++) {
            answer = Math.min(answer, DP[n-1][j]);
        }
        System.out.println(answer);
    }
}

 

---

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

12852번: 1로 만들기 2

동적계획법 문제 2

- 처음엔 이 경로를 쭉 출력해주는 걸 보고 탐색을 해야하나 했지만 시간제한 0.5초이다. 즉, 동적계획법으로 풀어야한다..

- before[] 을 사용해주는걸로 손쉽게 풀 수 있는 문제였다... 이게 생각이 안나서 한참 고민하다 검색하여 다른 사람의 코드를 보고 푼 문제이다. 

- DP[] 에는 해당 숫자가 되기까지 걸리는 최소 연산횟수를 저장한다. 

- before[] 배열에는 i 다음에 올 숫자를 저장한다고 생각하면된다. 예를 들어, before[ 6 ] : 2이므로 나중에 경로 출력할 때 역순으로 6 - >  2 이런식으로 출력하면 된다.

import java.util.*;
public class p12852 {
    // 복잡하게 그래프 탐색까지 가지 말고..그냥 DP 선에서 끝낼 수 있다. before[] 배열 하나 만들어서!
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] DP = new int[n+1];
        int[] before = new int[n+1];

        DP[1] = 0;
        before[1] = 1;

        for (int i = 2; i <= n; i++) {
            DP[i] = DP[i-1] + 1;
            before[i] = i-1;
            if (i % 3 == 0) {
                if (DP[i] > DP[i/3] + 1) {
                    DP[i] = DP[i/3] + 1;
                    before[i] = i/3;
                }
            }
            if (i % 2 == 0) {
                if (DP[i] > DP[i/2] + 1) {
                    DP[i] = DP[i/2] + 1;
                    before[i] = i/2;
                }
            }
        }

        System.out.println(DP[n]);

        while (n != 1) {
            System.out.print(n + " ");
            n = before[n];
        }
        System.out.print(1);
    }
}

---

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

17135번: 캐슬 디펜스

 

- 삼성 A형 문제,, 항상 조건을 잘 봐야하는 문제이다. 

이게 왜 실수했었냐면... pq에서 가장 우선순위가 높은 적을 먼저 죽이는데 각 사수마다 우선순위 높은 적이 같다면 그냥 같이 쏘는 것이었다. 나혼자 상상의 나래로 얘는 1순위 적 죽이고 다음 애가 만약 겹친담녀 다음 궁수는 2순위 적 죽이고 이런식으로 상상하였다.

while (!pq.isEmpty()) 이렇게 주면서 정확도 한30%쯤인가.. 거기서 계속 막혔었다. 

그리고 추가로 적과의 거리 정보 + 몇 번째 적인지 index 도 위치정보와 함께 저장해야 하는데 이것도 계속 고민했었다.

근데 그냥 ... static class 하나 더 형성하면 쉽게 해결할 수 있었다. 그래서 위치정보 Pos 클래스와 더불어 Monster라는 코드도 썼다. 

새로운 클래스 쓰는건 다른 분 코드 보다가 클래스에 저렇게 다 넣는거 보고 Pos만 만들줄 알고 ㅋㅋㅋ 클래스 하나 더 만들 줄 모르는 본인이 우스워졌다.. 

 

 

 

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

public class p17135 {
    static int[][] map;
    static int[] archerPos;
    static int row, col, shootDis, killCount;
    static ArrayList<Pos> enemyPos;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        shootDis = Integer.parseInt(st.nextToken());
        killCount = 0;

        map = new int[row][col];
        archerPos = new int[3];
        enemyPos = new ArrayList<>();

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    enemyPos.add(new Pos(i, j));
                }
            }
        }

        chooseArcherPos(0,0 );
        System.out.println(killCount);
    }

    public static void chooseArcherPos(int depth, int start) {
        if (depth == 3) {
            killCount = Math.max(killCount, game());
            return;
        }

        for (int i = start; i < col; i++) {
            archerPos[depth] = i;
            chooseArcherPos(depth+1, i+1);
        }
    }


    // 시뮬레이션
    public static int game() {
        int count = 0;
        ArrayList<Pos> enemies = new ArrayList<>(enemyPos);

        while (!enemies.isEmpty()) {
            if (count >= enemyPos.size()) {
                break;
            }
            ArrayList<Pos> temp = new ArrayList<>();
            boolean[] killed = new boolean[enemies.size()];
            for (int i = 0; i < 3; i++) {
                Pos archer = new Pos(row, archerPos[i]);
                PriorityQueue<Monster> pq = new PriorityQueue<>();

                for (int e = 0; e < enemies.size(); e++) {
                    int dis = distance(archer, enemies.get(e));
                    if (dis <= shootDis) {
                        pq.add(new Monster(dis, e, enemies.get(e)));
                    }
                }

                // 여기때문에 실수...
                if (!pq.isEmpty()) {
                    Monster poll = pq.poll();
                    if (!killed[poll.index]) {
                        killed[poll.index] = true;
                    }
                }
            }

            for (int i = 0; i < enemies.size(); i++) {
                if (!killed[i]) {
                    temp.add(enemies.get(i));
                }
                else {
                    count++;
                }
            }

            enemies = new ArrayList<>(moveEnemy(temp));

        }

        return count;
    }


    // 적 관련 함수
    public static ArrayList<Pos> moveEnemy(ArrayList<Pos> copyEnemyPos) {
        ArrayList<Pos> temp = new ArrayList<>();

        for (Pos p : copyEnemyPos) {
            Pos next = new Pos(p.x + 1, p.y);
            if (canMoveTo(next)) {
                temp.add(next);
            }
        }
        return temp;
    }

    public static boolean canMoveTo(Pos pos) {
        if (pos.x >= row) {
            return false;
        }
        return true;
    }

    // 거리계산 & 좌표 클래스 정의
    public static int distance(Pos x, Pos y) {
        return (Math.abs(x.x - y.x) + Math.abs(x.y - y.y));
    }

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

    }

    static class Monster implements Comparable<Monster> {
        int distance;
        int index;
        Pos pos;

        Monster(int d, int index, Pos p) {
            this.distance = d;
            this.index = index;
            this.pos = p;
        }

        @Override
        public int compareTo(Monster o) {
            if (this.distance == o.distance) {
                return this.pos.y - o.pos.y;
            }
            return this.distance - o.distance;
        }
    }
}