Per ardua ad astra !
I'm On My Way
Per ardua ad astra !
전체 방문자
오늘
어제
  • 분류 전체보기 (126)
    • Algorithm (50)
      • 백준 (30)
      • SWEA (3)
      • JUNGOL (3)
      • Programmers (5)
      • LeetCode (2)
    • 안드로이드 개발 (6)
      • Java로 개발 (0)
      • Kotlin으로 개발 (3)
    • Spring (41)
      • Spring기본 (17)
      • JPA기본 (15)
      • JPA활용 SpringBoot 기본 (9)
      • API 개발 기본 (0)
    • 네트워크 (3)
    • 운영체제 (0)
    • Life (3)
      • 책 (0)
      • 자기계발 (1)
      • 일상 (2)
    • 노마드코더 (3)
      • python으로 웹 스크래퍼 만들기 (3)
    • 프로그래밍 언어 (17)
      • Java 기본 (2)
      • 코틀린 기본 (15)

블로그 메뉴

  • 홈
  • 방명록

인기 글

hELLO · Designed By 정상우.
Per ardua ad astra !

I'm On My Way

Algorithm

[Java] BaekJoon 12869. 뮤탈리스크 (골드4) (dfs) (dp)

2021. 8. 14. 12:39

문제 출처: 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을 계속 생성해야 한다는 문제점이 존재한다. 메모리 초과가 발생한다.

 

    'Algorithm' 카테고리의 다른 글
    • [Java] BaekJoon 14226. 이모티콘 (BFS) (골드5)
    • [Java] BaekJoon 3197. 백조의호수(BFS) (플레5)
    • [Java] BaekJoon 2696 중앙값 구하기 (골드2) (힙에 대한 이해)
    • [Java] BaekJoon 2579. 계단오르기 (DP) (실버3)
    Per ardua ad astra !
    Per ardua ad astra !
    개발자 지망생이며 열심히 공부하고 기억하기 위한 블로그입니다.

    티스토리툴바