📙[Algo] 24.05.30 알고리즘

알고리즘 문제) BOJ 1516. 게임개발

• 링크 : https://www.acmicpc.net/problem/1516

문제 요약

• 어떤 건물을 짓기 위해서는 다른 건물을 먼저 지어야할 수 있음
• N개의 건물이 완성되기까지 걸리는 최소 시간 구하기

시간 제한

• 2초

입력

• 건물의 종류 수 N(1 ≤ N ≤ 500)
• N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호
  • 건물의 번호는 1부터 N
  • 각 줄은 -1로 끝난다
  • 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수

출력

• N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력

접근법

• 위상정렬
• 그러나 주어진 테케말고 또 다른 테케를 생각해야 한다.
  • 만약 아래와 같은 구조일때, 건물 C에 영향을 주는 시간은 뭐가 될까?
    

    

  • 부모 건물 A보다 건물 B가 시간이 더 오래걸리므로, 결국, B건물의 시간에 영향을 받게 된다.
  • 따라서, C건물 짓는 시간에는 B건물이 걸리기까지의 시간을 더해줘야한다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int[] arr = new int[N + 1];
        ArrayList<Integer>[] lst = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            lst[i] = new ArrayList<>();
        }
        int[] pCnt = new int[N + 1];

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

            while (true) {
                p = Integer.parseInt(st.nextToken());

                if (p == -1) break;

                pCnt[i]++;
                lst[p].add(i);
            }
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return o1[1] - o2[1];
            }
        });

        for (int i = 1; i <= N; i++) {
            if (pCnt[i] == 0) {
                pq.offer(new int[]{i, arr[i]});
            }
        }

        int cur, curTime;
        int[] ans = new int[N + 1];
        while (!pq.isEmpty()) {
            cur = pq.peek()[0];
            curTime = pq.poll()[1];

            ans[cur] = curTime;

            for (Integer nxt : lst[cur]) {
                pCnt[nxt]--;

                if (pCnt[nxt] == 0) {
                    pq.offer(new int[]{nxt, arr[nxt] + curTime});
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(ans[i]).append("\n");
        }

        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 27925. 인덕션

• 링크 : https://www.acmicpc.net/problem/27925

문제 요약

• 요리 공간은 세 개 존재
• 각 음식을 요리하려면 정확한 온도가 필요하다.
• 온도는 다음과 같은 규칙으로 조절한다
  • 온도는 정수이며 0~9 사이 값
  • 처음 모든 요리 공간의 온도는 0
    • 누르면 1감소, + 누르면 1증가
  • 온도가 0일 때 -를 누르면 9, 9에서 +를 누르면 0
  • 모든 요리를 순서대로 완성하기 위해 눌러야하는 온도 조절 버튼의 최소 횟수는?

시간 제한

• 1초

입력

• 음식 개수 N
  • 1 ≤ N ≤ 5000
• 각 음식을 요리하기 위해 필요한 온도를 나타내는 N개 정수 t1~tN이 공백으로 구분되어 주어짐
  • 0 ≤ ti ≤ 9

출력

• 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 출력

접근법

• 9 3 8 1 0
  • 0 → 9 → 8
  • 0 → 1 → 2 → 3
  • 0 → 1 → 0
• 각 음식별로 공간 1~3에서 +버튼 또는 -버튼 누르는 모든 경우를 탐색하면서 가장 최소 버튼 횟수를 반환시키게끔 했다.
  • 이때, 4차원 dp배열에 메모이제이션을 하면서 시간을 단축 시켰다.
    • dp[cur][place1][place2][place3] → cur번째 음식에서 공간의 온도가 각각 pace1, place2, place3일 때의 가장 최소의 버튼 횟수 저장

코드

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

public class Main {
    static int N;
    static int[] foods;
    static int[][][][] dp;

    static int recur(int cur, int place1, int place2, int place3) {
        if (cur == N) return 0;

        if (dp[cur][place1][place2][place3] != -1) return dp[cur][place1][place2][place3];

        int ret = 1 << 30;
        int temp, cnt1, cnt2;
        int[] place = {place1, place2, place3};
        for (int i = 0; i < 3; i++) {
            temp = place[i];

            // + 버튼 누르기
            cnt1 = 0;
            while (place[i] != foods[cur]) {
                place[i]++;
                cnt1++;
                if (place[i] == 10) place[i] = 0;
            }
            ret = Math.min(ret, recur(cur + 1, place[0], place[1], place[2]) + cnt1);

            // - 버튼 누르기
            place[i] = temp;
            cnt2 = 0;
            while (place[i] != foods[cur]) {
                place[i]--;
                cnt2++;
                if (place[i] == -1) place[i] = 9;
            }
            ret = Math.min(ret, recur(cur + 1,  place[0], place[1], place[2]) + cnt2);

            place[i] = temp;
        }

        dp[cur][place1][place2][place3] = ret;
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

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

        dp = new int[N][10][10][10];
        for (int[][][] d1 : dp) {
            for (int[][] d2 : d1) {
                for (int[] d3 : d2) {
                    Arrays.fill(d3, -1);

                }
            }
        }

        System.out.println(recur(0,0,0,0));

        br.close();
    }
}