문제 출처: https://www.acmicpc.net/problem/12869
12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
문제 이해
목표
(1<=N<=3)개의 scv가 주어지고 scv의 초기 체력은 60이하의 자연수 이다.
뮤탈리스크가 한대를 때릴 때 각각의 scv에게 9, 3, 1의 데미지를 줄 수 있다고 할 때
최소한으로 때려서 SCV를 다 죽일 수 있도록 해보자
풀이
- 이전의 출근기록 문제와 비슷하다. dfs로 때리는 경우의 수를 탐색하되 visited(dp)를 통해 가지치기를 하여 탐색을 줄인다.
visitied를 효과적으로 사용하기 위해서, visited[max][mid][min]으로, 즉 첫번째 배열자리엔 max, 두번째 배열자리엔 mid, 3번째 배열자리엔 min을 검사할 수 있도록, 항상 max, mid, min 값을 구하고 정렬하여 방문처리를 더 효율적으로 검사할 수 있도록 한다.
ex) 체력이 60 60 60인 scv가 있으면
(60 - 9, 60 - 3, 60 -1)
(60 - 9, 60 - 1, 60 -3)
(60 - 3, 60 - 9, 60 -1) .. 모두 dfs로 들어갔을 때 max: 59, mid: 57, min: 51로 같다.
따라서 가장 처음 들어갔을 때 정렬하고 visited처리하면, 다른 순서로 값이 들어와도 그 값이 일치만 한다면 또 탐색하지 않으므로, 효과적인 코드가 된다. (60 - 9, 60 - 3, 60 -1) 이후에는 모두 가지치기되어 탐색을 하지 않는다. - 매개변수에 각각의 scv의 체력을 넣어서 배열을 대신에 사용하여 메모리 초과를 방지한다.
소스코드
성공한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 뮤탈리스크 {
private static int N;
private static int answer;
private static boolean[][][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[] scvs = new int[3];
String[] strArr = br.readLine().split(" ");
int max = 0;
for (int i = 0; i < N; i++) {
scvs[i] = Integer.parseInt(strArr[i]);
max = Math.max(scvs[i], max);
}
max += 1;
visited = new boolean[max][max][max];
for (int i = N; i < 3; i++) {
scvs[i] = 0;
}
answer = Integer.MAX_VALUE;
dfs(scvs[0], scvs[1], scvs[2], 0);
System.out.println(answer);
}
private static void dfs(int scv1, int scv2, int scv3, int count) {
if (scv1 <= 0 && scv2 <= 0 && scv3 <= 0) {
if (count < answer) {
answer = count;
}
return;
}
scv1 = Math.max(0, scv1);
scv2 = Math.max(0, scv2);
scv3 = Math.max(0, scv3);
int max = Math.max(scv1, Math.max(scv2, scv3));
int min = Math.min(scv1, Math.min(scv2, scv3));
int mid = scv1 + scv2 + scv3 - max - min;
if (visited[max][mid][min] || answer <= count) {
return;
}
visited[max][mid][min] = true;
dfs(max - 9, mid - 3, min - 1, count + 1);
dfs(max - 9, mid - 1, min - 3, count + 1);
dfs(max - 3, mid - 9, min - 1, count + 1);
dfs(max - 3, mid - 1, min - 9, count + 1);
dfs(max - 1, mid - 9, min - 3, count + 1);
dfs(max - 1, mid - 3, min - 9, count + 1);
}
}
초기 잘못 짜여진 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class 뮤탈리스크fail {
private static int[] scv;
private static int N;
private static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
scv = new int[N];
ArrayList<Integer> remain = new ArrayList<>();
String[] str = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
scv[i] = Integer.parseInt(str[i]);
remain.add(i);
}
ArrayList<Integer> hits = getHits(N);
answer = Integer.MAX_VALUE;
dfs(hits, scv, remain, 0);
System.out.println(answer);
}
private static void dfs(ArrayList<Integer> hits, int[] scv, ArrayList<Integer> remain, int tempAnswer) {
if(tempAnswer >= answer){
return;
}
// 9 3 1이 모두 히트했는지 확인 (3대모두 때렸는지)
if (hits.isEmpty() || remain.isEmpty()) {
for (int i = 0; i < N; i++) {
if (scv[i] > 0) {
remain.add(i);
}
}
hits = getHits(remain.size());
tempAnswer++;
}
// scv 다죽었는지 검사
boolean check = true;
for (int s : scv) {
if (s > 0) {
check = false;
break;
}
}
if (check) {
if (answer > tempAnswer) {
answer = tempAnswer;
}
return;
}
//3
//12 10 4
for (int i : remain) { // 아직 맞지 않은 scv 인덱스를 나타내는 i
ArrayList<Integer> remainClone = (ArrayList<Integer>) remain.clone();
remainClone.remove(Integer.valueOf(i));
for (Integer hit : hits) { // 9 3 1 중
ArrayList<Integer> hitsClone = (ArrayList<Integer>) hits.clone();
scv[i] -= hit;
hitsClone.remove(Integer.valueOf(hit));
dfs(hitsClone, scv, remainClone, tempAnswer);
scv[i] += hit;
}
}
}
public static ArrayList<Integer> getHits(int n){
ArrayList<Integer> hits = new ArrayList<>();
hits.add(9);
if (n == 2) {
hits.add(3);
} else if (n == 3) {
hits.add(3);
hits.add(1);
}
return hits;
}
}
dfs에 ArrayList를 사용해서 dfs를 적용하려면 clone을 계속 생성해야 한다는 문제점이 존재한다. 메모리 초과가 발생한다.