백준 1149, 12852, 17135
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
동적계획법 문제
- 각 색칠 비용 저장할 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
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
www.acmicpc.net
동적계획법 문제 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번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
- 삼성 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;
}
}
}