[백준 Gold 3] 1516 게임 개발 - Java

문제링크 : https://www.acmicpc.net/problem/status/1516

1516번 맞힌 사람 - 1 페이지

 

접근 과정 : 

• 어떤 건물을 짓기 전에, 지어야 하는 건물이 있다면 그 건물들을 모두 먼저 지어야 한다.
• 건물을 지을 수 있는 상황이라면, 여러 건물을 동시에 지을 수 있다.
• 즉, A건물을 짓기 위해서는 A건물을 짓는 시간 + (먼저 지어야하는 건물들의 최대시간) 이다.

 

1. 각 건물의 시간을 저장하고, 먼저 지어야 하는 건물들을 저장한다.
2. 해당 건물보다 먼저 지어햐 하는 건물들을 순회하면서 먼저 필요한 최대 시간을 구한다.
3. 해당 건물을 짓는 시간에 먼저 필요한 최대 시간을 더해서 리턴한다.
4. 계산된 건물의 시간은 DP배열에 저장하여, 재계산하지 않도록 한다.

   ** 먼저 지어야 하는 건물리스트를 저장하는 방법

     1) Build클래스를 생성하여 노드처럼 엮어서 건물들의 관계를 저장하고 접근한다.

     2) List<List>에 각 건물의 먼저 지어야 하는 건물 리스트를 저장한다.

 

소스 코드 및 결과 :

package BOJ;

/**
 * 게임 개발
 
 	Build클래스와 Build[] BuildSequence를 통해 건물들간의 관계를 엮는다.
    그리고 이를 통해 먼저 지어야하는 건물에 접근한다.
*/

import java.io.*;
import java.util.*;

public class BOJ1516 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        new BOJ1516().solution();

    }

    void solution() throws NumberFormatException, IOException {

        init();

        StringBuilder answer = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            answer.append(getNeedTime(i)).append("\n");
        }
        System.out.println(answer.toString().trim());

    }

    int N;
    int[] time;
    Build[] buildSequence;
    int[] dp;

    private class Build {
        int num;
        Build previous;

        Build(int num, Build previous) {
            this.num = num;
            this.previous = previous;
        }
    }

    void addSequence(int num, int previousNum) {

        if (buildSequence[num] == null) {
            buildSequence[num] = new Build(previousNum, null);
        } else {
            buildSequence[num] = new Build(previousNum, buildSequence[num]);
        }
    }

    void init() throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        time = new int[N + 1];
        buildSequence = new Build[N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());

            while (true) {
                int x = Integer.parseInt(st.nextToken());
                if (x == -1) {
                    break;
                }

                addSequence(i, x);
            }
        }

        dp = new int[N + 1];
    }

    int getNeedTime(int num) {

        if (dp[num] != 0) {
            return dp[num];
        }

        dp[num] = time[num];

        int need = 0;

        for (Build previous = buildSequence[num]; previous != null; previous = previous.previous) {

            need = Math.max(need, getNeedTime(previous.num));
           
        }

        return dp[num]+=need;
    }
}

 

package BOJ;

/**
 * 
 * 게임 개발
 
 	List<List>를 통해 각 건물들의 먼저 지어햐 하는 건물리스트를 저장한다.
 * 
*/

import java.io.*;
import java.util.*;

public class BOJ1516_copy {

    public static void main(String[] args) throws NumberFormatException, IOException {

        new BOJ1516_copy().solution();

    }

    void solution() throws NumberFormatException, IOException {

        init();

        StringBuilder answer = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            answer.append(getNeedTime(i)).append("\n");
        }
        System.out.println(answer.toString().trim());

    }

    int N;
    int[] time;
    List<List<Integer>> previous;
    int[] dp;

    void init() throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        time = new int[N + 1];
        previous = new ArrayList<>();
        previous.add(new ArrayList<>());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            previous.add(new ArrayList<>());

            while (true) {
                int x = Integer.parseInt(st.nextToken());
                if (x == -1) {
                    break;
                }

                previous.get(i).add(x);
            }
        }

        dp = new int[N + 1];
    }

    int getNeedTime(int num) {

        if (dp[num] != 0) {
            return dp[num];
        }

        dp[num] = time[num];

        int need = 0;

        for (int p : previous.get(num)) {
            need = Math.max(need, getNeedTime(p));
        }

        return dp[num] += need;
    }
}

 

P.S 

전반적인 방법의 차이는 없지만, 건물들의 관계 저장 방식에서 시간차이가 발생한다.

추가로 List<List> 대신 Map<Int, Set>구조를 쓰면 약간 더 많은 시간이 소모된다.

접근 방식에서 차이가 효율성 차이가 나는 것 같다.