11049번: 행렬 곱셈 순서

N(1≤N≤500) 개의 행렬이 주어졌을 때 어떤 순서로 곱셈을 해야 연산 횟수를 최소화할 수 있을까?

예를 들어 A가 5x3이고 B가 3x2, C가 2x6인 경우를 생각해보자.

우선 (AB) C는 5x2 AB를 만들기 위해 5x3x2의 연산 횟수가 필요하고 5x2 AB와 2x6C가 곱해져 최종적으로 5x6이 나오는데 여기에 5x2x6의 연산 횟수가 필요하다.

최종적으로 5x3x2 + 5x2x6 = 90번의 연산이다.

그런데 이 연산을 A(BC)로 하면 3x2x6 + 5x3x6 = 126이 된다. 같은 곱셈이지만 곱셈 연산 수가 다르다.

우선 완전 탐색을 고려할 수 있다. 하지만 너무 많다..

생각해 보면 ABCD가 있을 때 (AB)(CD)가 있을 수 있고 ((AB) C) D가 있을 수 있다. AB가 반복해서 나온다. 즉 DP를 사용하면 될 것 같다.

상태를 생각해 보자. i 번째까지의 최소 연산 횟수를 저장하면 될까?

아니다. 앞에서부터 계산한다고 결과가 최소가 되지 않는다.

i부터 j까지의 연산을 기록하자..

그렇다면 dp[i][j]를 어떻게 정의할까?

dp[i][j]: i 번째 행렬부터 j번째 행렬까지 곱하는데 필요한 최소 연산 횟수

dp[i][j] = min(dp[i][k] + dp[k+1][j] + (i x k x j))가 된다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ11049 {

    static FastReader scan = new FastReader();
    static int N;
    static int[][] matrices;

    static void input() {
        N = scan.nextInt();
        matrices = new int[N][2];
        for (int i = 0; i < N; i++) {
            matrices[i] = new int[]{scan.nextInt(), scan.nextInt()};
        }
    }

    static void solve() {
        int[][] dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }

        System.out.println(recFunc(0, N - 1, dp));
    }

    static int recFunc(int start, int end, int[][] dp) {
        if (start == end) {
            return 0;
        }

        if (dp[start][end] != -1) {
            return dp[start][end];
        }

        dp[start][end] = Integer.MAX_VALUE;
        for (int mid = start; mid < end; mid++) {
            int leftCost = recFunc(start, mid, dp);
            int rightCost = recFunc(mid + 1, end, dp);
            int mergeCost = matrices[start][0] * matrices[mid][1] * matrices[end][1];

            dp[start][end] = Math.min(dp[start][end], leftCost + rightCost + mergeCost);
        }
        return dp[start][end];
    }

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

6087번: 레이저 통신

c 끼리 레이저로 통신하기 위해 설치해야 하는 거울 개수의 최솟값.

‘/’, ‘\’을 설치해 방향을 90도 회전할 수 있다.

시작점과 도착점이 존재하며 두 점 중 어느 점에서 레이저를 쏴도 상관없다.

시작점에서 도착점까지 도달하는 수많은 경로들이 있다 이 중에 꺾이는 코너가 최소한인 경로를 찾으면 될 것 같다.

꺾이는 코너를 어떻게 판단할까? → 이동 방향을 기록하고 비교를 통해 가능하다.

두 점 사이의 거울 개수를 최소로 하는 것이 최단거리와 관련 있을까? → 최단거리보다 긴 거리인데 거울의 개수가 적게 들어가는 경우가 존재하는지 생각해봐야 한다. 최단거리가 아니라는 것은 코너링이 더 추가된다는 뜻이기에 최단거리일 때 답 후보가 있다.

1. 최단거리를 구해야 하기 때문에 bfs를 사용하겠다.
2. 최단거리로 도착점에 도달했을 때의 코너 개수를 갱신한다.
3. 같은 지점이라도 여러 방향에서 도달할 수 있고 도달하는데 들어간 코너 개수가 다를 수 있다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ6087 {

	static class Point {
		int r;
		int c;
		int d;
		int count;

		public Point(int r, int c, int d, int count) {
			this.r = r;
			this.c = c;
			this.d = d;
			this.count = count;
		}

		boolean isGoal() {
			return this.r == goal[0] && this.c == goal[1];
		}
	}
	static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static FastReader scan = new FastReader();
	static int W, H;
	static char[][] map;
	static int[] start;
	static int[] goal;
	static int[][] cPos;

    static void input() {
		W = scan.nextInt();
		H = scan.nextInt();
		map = new char[H][W];
		cPos = new int[2][2];
		int idx = 0;
		for (int i = 0; i < H; i++) {
			map[i] = scan.next().toCharArray();
			for (int j = 0; j < W; j++) {
				if (map[i][j] == 'C') {
					cPos[idx++] = new int[]{i, j};
				}
			}
		}
		start = cPos[0];
		goal = cPos[1];
    }

	static void bfs(int[] start) {
		Queue<Point> q = new ArrayDeque<>();
		int[][][] visited = new int[H][W][4];
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				Arrays.fill(visited[i][j], Integer.MAX_VALUE);
			}
		}

		for (int d = 0; d < 4; d++) {
			q.add(new Point(start[0], start[1], d, 0));
			visited[start[0]][start[1]][0] = 0;
 		}

		int mirrorCount = Integer.MAX_VALUE;
		while (!q.isEmpty()) {
			Point curr = q.poll();
			if (curr.isGoal()) {
				mirrorCount = Math.min(mirrorCount, curr.count);
				continue;
			}

			for (int d = 0; d < 4; d++) {
				int nr = curr.r + DIRECTION[d][0];
				int nc = curr.c + DIRECTION[d][1];

				if (!inRange(nr, nc)) continue;
				if (isWall(nr, nc)) continue;

				int nextCount = curr.count;
				if (!isStart(curr.r, curr.c) && isConner(curr.d, d)) {
					nextCount++;
				}

				if (visited[nr][nc][d] > nextCount) {
					visited[nr][nc][d] = nextCount;
					q.add(new Point(nr, nc, d, nextCount));
				}
			}
		}

		System.out.println(mirrorCount);
	}

	static boolean isStart(int r, int c) {
		return start[0] == r && start[1] == c;
	}

	static boolean isConner(int d1, int d2) {
		if (d1 == 0) {
			return d2 != 0 && d2 != 1;
		} else if (d1 == 1) {
			return d2 != 0 && d2 != 1;
		} else if (d1 == 2) {
			return d2 != 2 && d2 != 3;
		} else {
			return d2 != 2 && d2 != 3;
		}
	}

	static boolean inRange(int r, int c) {
		return r >= 0 && r < H && c >= 0 && c < W;
	}

	static boolean isWall(int r, int c) {
		return map[r][c] == '*';
	}

    public static void main(String[] args) {
		input();
		bfs(start);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

10021번: Watering the Fields

N개의 필드 존재 (1 ≤ N ≤ 2000)

각 필드는 2차원 평면상 (xi, yi)로 표시(0≤ xi, yi ≤ 1000)

$$ i,j 필드 사이 비용 = (x_i-x_j)^2 + (y_i-y_j)^2 $$

모든 필드를 최소비용으로 연결하고 싶다.

그런데 비용이 C 이상인 파이프만 설치할 수 있다. (1≤ C≤ 1,000,000)

크루스칼 알고리즘을 사용하면 될 것 같다.

1. 주어진 정보로 간선을 계산해 저장한다.
2. 비용이 작은 간선부터 꺼내 두 노드를 연결한다.
3. 노드 연결 시 이미 같은 집합이거나 비용이 C보다 작다면 연결하지 않는다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ10021 {

    static class Edge {
        int from;
        int to;
        int cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return from + "," + to + "," + cost;
        }
    }

    static FastReader scan = new FastReader();
    static int N, C;
    static int[][] fields;
    static List<Edge>[] graph;

    static void input() {
        N = scan.nextInt();
        C = scan.nextInt();
        fields = new int[N][2];
        for (int i = 0; i < N; i++) {
            fields[i] = new int[]{scan.nextInt(), scan.nextInt()};
        }
    }

    static void initGraph() {
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 각 노드부터 출발한 거리 계산
        for (int i = 0; i < N; i++) {
            int[] from = fields[i];
            for (int j = i + 1; j < N; j++) {
                int[] to = fields[j];
                int cost = calcCost(from, to);
                graph[i].add(new Edge(i, j, cost));
            }
        }
    }

    static int calcCost(int[] from, int[] to) {
        return (int) (Math.pow((from[0] - to[0]), 2) + Math.pow((from[1] - to[1]), 2));
    }

    static void solve() {
        int totalCost = 0;
        int edgeCount = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.cost));
        for (int i = 0; i < N; i++) {
            for (Edge e : graph[i]) {
                if (e.cost < C) continue;
                pq.add(e);
            }
        }
        int[] parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            int from = curr.from;
            int to = curr.to;
            int cost = curr.cost;

            if (isConnected(parent, from, to)) {
                continue;
            }

            union(parent, from, to);
            totalCost += cost;
            edgeCount++;
        }

        System.out.println(edgeCount == N - 1 ? totalCost : -1);
    }

    static boolean isConnected(int[] parent, int x, int y) {
        return find(parent, x) == find(parent, y);
    }

    static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);

        if (rootX < rootY) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
        }
    }

    static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    public static void main(String[] args) {
        input();
        initGraph();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

2292번: 벌집

중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는가.

해당 수가 몇 레벨에 존재하는 지를 알아야 한다.

1 → 1 레벨

2 ~ 7 → 2 레벨

8 ~ 19 → 3 레벨

20 → 37 → 4 레벨 이런 식으로 증가하고 있다. N = 13 이면 3 레벨에 존재하기 때문에 답은 3이다. 그리고 N = 58이면 5 레벨에 있기 때문에 답은 5이다.

육각형으로 증가하는데 1 레벨은 길이가 1인 육각형, 2 레벨을 길이가 2인 육각형이다.

3 레벨은 3*6 - 6이다. 즉 해당 레벨에 존재하는 칸의 개수는 6 * (X - 1) 단, X = 1 이면 1이 된다.

2 계층은 6개 3 계층은 12개가 존재한다.

마지막 번호도 규칙이 있다.

1번 레벨 : 1

2번 레벨 : 7

3번 레벨 : 19

4번 레벨 : 37

이렇게 된다. 즉 이전 마지막 번호 + (6 * (X-1))이다.

이제 주어진 N이 어느 범위인지 판단하면 된다. 마지막 숫자보다 작으면 가능한 후보이며 마지막 숫자보다 큰 순간이면 바로 이전 레벨이 답이다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2292 {

    static FastReader scan = new FastReader();
    static int N;

    static void input() {
        N = scan.nextInt();
    }

    static void solve() {
        int level = 2;
        int end = 1;

        while (end < N) {
            end += 6 * (level - 1);
            level++;
        }

        System.out.println(level - 1);
    }

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

2933번: 미네랄

동굴 내에서 막대 던지기를 한다. 막대는 미네랄을 파괴할 수도 있다.

R행 C열의 동굴. 각 칸은 빈칸 혹은 미네랄. 네 방향 중 하나로 인접한 미네랄 = 같은 클러스터

번갈아가며 막대를 던진다. 막대를 던지기 전에 던질 높이를 정한다. 막대는 땅과 수평을 이루며 날아간다.

날아가는 도중에 미네랄을 만나면 그 칸의 미네랄은 모두 파괴되며 막대는 그 자리에서 멈춘다.

클러스터라는 개념이 등장한다. 미네랄이 파괴된 이후 남은 클러스터가 분리될 수 있다고 하는데 이 부분부터 이해가 필요하다.

지도가 2차원 평면을 나타내는 것이 아니라 세로가 높이를 나타내고 있다.

막대를 던지는 높이는 1 ~ R 사이로 주어지며 이를 통해서 미네랄이 상하로 갈라지는 것이다.

필요한 기능

1. 턴을 구분한다.→ height를 순회하면서 %2 == 0 이면 left → right이다.
2. 막대를 던지는 기능 → height가 r이 돼서 거기부터 c를 증가시켜 가며 처음 미네랄을 만나는 곳을 찾는다.
3. 미네랄 클러스터 판단 클러스터를 확인할 수 있어야 한다. 클러스터가 하강하는 경우 = 바닥과 연결이 안 돼 있다.
   1. 미네랄과 충돌할 시 해당 위치의 4방향 기준 시작점으로 추가한 뒤 탐색을 시작
   2. 탐색 중 바닥과 연결되지 않은 것이 하강하는 클러스터
4. 하강할 클러스터를 어떻게 하강시키는가? 떨어지는 동안 클러스터의 모양이 유지된다.
   1. 떨어지다가 바닥에 도달하지 않았는데 다른 미네랄에 걸리는 경우
   2. 걸리지 않고 가장 아래 부분이 바닥에 도달하는 경우

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2933 {

    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //상하좌우
    static FastReader scan = new FastReader();
    static int R, C, N;
    static char[][] initialMap;
    static int[] heights;

    static class Result {
        boolean isDown;
        List<int[]> cand;

        public Result(boolean isDown, List<int[]> cand) {
            this.isDown = isDown;
            this.cand = cand;
        }
    }

    static void input() {
        R = scan.nextInt();
        C = scan.nextInt();
        initialMap = new char[R][C];
        for (int i = 0; i < R; i++) {
            initialMap[i] = scan.next().toCharArray();
        }
        N = scan.nextInt();
        heights = new int[N];
        for (int i = 0; i < N; i++) {
            heights[i] = R - scan.nextInt(); // 높이
        }
    }

    static void print(char[][] map) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < map.length; i++) {
            sb.append(map[i]);
            if (i != map.length -1) {
                sb.append("\\n");
            }
        }
        System.out.println(sb);
    }

    static void solve(char[][] map) {
        for (int i = 0; i < N; i++) {
            int height = heights[i];
            int[] target;
            if (i % 2 == 0) {
                target = findMineral(map, height, 0);
            } else {
                // right to left
                target = findMineral(map, height, 1);
            }
            if (target == null) {
                continue; // 맞은 미네랄이 없다.
            }

            map[target[0]][target[1]] = '.';

            // 해당 타겟 기중 상하좌우를 보고 하강 클러스터 후보 찾기
            List<int[]> cand = new ArrayList<>();
            for (int d = 0; d < 4; d++) {
                int nr = target[0] + DIRECTION[d][0];
                int nc = target[1] + DIRECTION[d][1];
                if (!inRange(nr, nc)) {
                    continue;
                }
                if (map[nr][nc] == 'x') {
                    cand.add(new int[]{nr, nc});
                }
            }

            if (cand.isEmpty()) {
                // 상하좌우에 연결된 미네랄이 없다 -> 클러스터 후보가 없다.
                continue;
            }

            List<List<int[]>> clusters = new ArrayList<>();
            boolean[][] visited = new boolean[R][C];

            for (int[] mineral : cand) {
                if (!visited[mineral[0]][mineral[1]]) {
                    Result result = findDownCluster(map, mineral);
                    if (result.isDown) {
                        clusters.add(result.cand);
                    }
                    for (int[] pos : result.cand) {
                        visited[pos[0]][pos[1]] = true;
                    }
                }
            }

            for (List<int[]> cluster : clusters) {
                for (int[] pos : cluster) {
                    map[pos[0]][pos[1]] = '.';
                }

                int minHeight = calcDownHeight(cluster, map);

                for (int[] pos : cluster) {
                    map[pos[0] + minHeight][pos[1]] = 'x';
                }
            }
        }
        print(map);
    }

    static int calcDownHeight(List<int[]> cluster, char[][] map) {
        int minHeight = Integer.MAX_VALUE;
        for (int[] pos : cluster) {
            int r = pos[0];
            int c = pos[1];
            int h = 0;
            r++;
            while (inRange(r, c) && map[r][c] != 'x') {
                h++;
                r++;
            }
            minHeight = Math.min(minHeight, h);
        }
        return minHeight;
    }

    static Result findDownCluster(char[][] map, int[] start) {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[R][C];
        q.add(start);
        visited[start[0]][start[1]] = true;
        List<int[]> cand = new ArrayList<>();
        boolean isBottom = false;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            cand.add(curr);
            int r = curr[0];
            int c = curr[1];
            if (r == R - 1) {
                // 밑바닥 도달
                isBottom = true;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + DIRECTION[d][0];
                int nc = c + DIRECTION[d][1];

                if (!inRange(nr, nc)) continue;
                if (visited[nr][nc]) continue;
                if (map[nr][nc] == 'x') {
                    q.add(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }
        }
        return isBottom ? new Result(false, List.of()) : new Result(true, cand);
    }

    static boolean inRange(int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C;
    }

    static int[] findMineral(char[][] map, int r, int dir) {
        if (dir == 0) {
            // left to right
            for (int i = 0; i < C; i++) {
                if (map[r][i] == 'x') {
                    return new int[]{r, i};
                }
            }
        } else {
            for (int i = C - 1; i >= 0; i--) {
                if (map[r][i] == 'x') {
                    return new int[]{r, i};
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        input();
        solve(copy(initialMap));
    }

    private static char[][] copy(char[][] initialMap) {
        return Arrays.stream(initialMap)
                .map(char[]::clone)
                .toArray(char[][]::new);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Coin Change - LeetCode

amount를 만드는데 필요한 최소 코인 개수를 찾아야 한다.

coins = [1, 2, 5], amount = 11 일 때

11 = 5 + 5 + 1 이 최소이다. 답은 3이다.

coins = [2], amount = 3 일 때

3은 2를 통해 만들 수 없기 때문에 -1이 답니다.

coins = [1], amount = 0이면 0개를 사용하면 되기 때문에 답은 0이다.

우선 greedy를 고려해 볼 수 있지만 각 동전은 대체가 불가능하기 때문에 최적해를 보장할 수 없다.

dp를 생각해 보자.

dp [i] = i원을 만드는데 필요한 최소 동전 개수이다.

첫 번째 예시에서 dp [11] = min(dp [6], dp [9], dp [10]) + 1 이렇게 된다.

정리하자면 dp [i] = min(dp [i], dp [i-coin] + 1), for coin in coins, dp [0] = 0이 된다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i-coin] != INF) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); 
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

Min Stack - LeetCode

stack을 구현하는 문제이다. 모든 작업이 O(1)의 시간복잡도로 가능해야 한다.

대부분의 기능은 stack을 쓰면 O(1)이 가능하지만 최솟값을 알아내야 하는 기능도 O(1)로 동작해야 한다는 점이 중요하다.

우선 최소값을 변수로 저장하는 방법을 생각해 보자.

이 방법은 최솟값을 바로 찾을 수는 있지만 최솟값이 갱신될 때 스택 내의 모든 요소를 순회해야 한다.

별도로 해당 레벨에서의 최솟값을 가지고 있어야 할 객체가 필요하다.

즉 삽입되는 값을 노드라고 생각했을 때 항상 노드 기준 최소값을 함께 기억하고 있는 것이다.

class MinStack {

    static class Node {
        int val;
        int min;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private Deque<Node> stack = new LinkedList<>();

    public MinStack() {
    }
    
    public void push(int val) {
        if (!stack.isEmpty()) {
            Node top = stack.peekLast();
            stack.addLast(new Node(val, Math.min(val, top.min)));
            return;
        }
        stack.addLast(new Node(val, val));
    }
    
    public void pop() {
        stack.pollLast();
    }
    
    public int top() {
        return stack.peekLast().val;
    }
    
    public int getMin() {
        return stack.peekLast().min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

15591번: MooTube (Silver)

1 ~ N까지의 동영상 존재(1≤N≤5,000)

연관 동영상 리스트를 만들기로 했다.

연관성 측정 = “USADO”

N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재.

임의의 두 쌍 사이의 동영상의 USADO = 그 경로의 모든 연결들의 USADO 중 최솟값

주어진 동영상에 대해 USADO가 K이상인 모든 동영상이 추천되도록 하려고 한다. 이때의 적절한 K값을 결정하려 한다.

USADO가 k일 때 i번 영상을 보고 있는 소들에게 몇 개의 동영상이 추천될지 출력하다.

우선 주어진 입력값 중 USADO인 r의 범위가 1≤r≤1,000,000,000이다. 10억으로 매우 크다.

동영상이 노드이며 양방향 가중치가 있는 그래프이다.

예제 입력을 보자.

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

일 때 1번과 2번은 USADO 3, 2번과 3번은 USADO 2, 2번과 4번은 USADO 4를 가지고 있다.

여기서 1번과 3번의 USADO를 계산해 보면 min(2, 3) = 2가 된다.

해당 경로에 있는 USADO 중 최소 값이다.

여기서 질문 4 1 이면 1번 기준 모든 USADO가 필요하다.

(1,2) = 3, (1,3) = 2, (1,4) = 3이며 k가 4이기 때문에 4 이상인 USADO가 없으므로 0개가 추천이 된다.

시작점부터 시작해 도달할 수 있는 모든 노드 사이에 비용이 k 이상인 것들의 개수를 세면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Edge {
        int to;
        int distance;

        Edge(int to, int distance) {
            this.to = to;
            this.distance = distance;
        }
    }

    static FastReader scan = new FastReader();
    static final int INF = Integer.MAX_VALUE;
    static int N, Q;
    static ArrayList<Edge>[] graph;
    static int[][] questions;

    static void input() {
        N = scan.nextInt();
        Q = scan.nextInt();
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList();
        }
        for (int i = 0; i < N - 1; i++) {
            int p = scan.nextInt() - 1;
            int q = scan.nextInt() - 1;
            int w = scan.nextInt();
            graph[p].add(new Edge(q, w));
            graph[q].add(new Edge(p, w));
        }

        questions = new int[Q][];

        for (int i = 0; i < Q; i++) {
            questions[i] = new int[]{scan.nextInt(), scan.nextInt() - 1}; //k, v
        }
    }

    static int bfs(int start, int k) {
        boolean[] visited = new boolean[N];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;
        int count = 0;

        while (!q.isEmpty()) {
            int curr = q.poll();

            for (Edge edge : graph[curr]) {
                if (!visited[edge.to]) {
                    int minUsado = Math.min(edge.distance, k);
                    if (minUsado >= k) {
                        visited[edge.to] = true;
                        q.add(edge.to);
                        count++;
                    }
                }
            }
        }
        return count;
    }

    static void solve() {
        for (int[] q : questions) {
            int k = q[0];
            int v = q[1];
            System.out.println(bfs(v, k));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

10830번: 행렬 제곱

N*N 크기의 행렬 A, A의 B제곱을 구하라. 수가 매우 커질 수 있으니 A^B의 각 원소를 1,000으로 나눈 나머지를 출력.

2≤N≤5, 1≤B≤100,000,000,000

B가 아주 크다. 단순한 방법으로는 안된다.

행렬 A의 B제곱은 A의 B-1 제곱에 A를 곱한 것이다. 팩토리얼과 유사하다. 그런데 B가 최대이면 단순하게 순회를 1번만 돌아도 시간초과이다.

B가 100만이라고 해보자 A^100만 = (A^50만)^2

$$ A^B = {A^{(B/2)}}^2 $$

이러면 B가 1천억이라 하더라도 500억 → 250억 → 125억 이렇게 logN으로 감소시킬 수 있다.

그런데 B가 홀수냐 짝수냐에 따라서 처리를 좀 달리해야 한다. B가 짝수라면 그냥 해도 되지만 B가 홀수라면 1일 빼서 짝수로 만든 다음 해당 과정을 처리하고 마지막에 하나를 다시 곱해준다.

필요한 연산들은 다음과 같다.

1. 행렬의 곱셈
2. 거듭제곱의 재귀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[][] matrix;
    static long B;
    static final int MOD = 1_000;

    static FastReader scan = new FastReader();

    static void input() {
        N = scan.nextInt();
        B = scan.nextLong();
        matrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = scan.nextInt() % MOD;
            }
        }
    }

    static int[][] multiply(int[][] A, int[][] B) {
        int[][] C = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
                }
            }
        }
        return C;
    }

    static int[][] power(int[][] A, long B) {
        if (B == 1) {
            return A;
        }

        int[][] tmp = power(A, B / 2);
        tmp = multiply(tmp, tmp);

        if (B % 2 == 1) {
            tmp = multiply(tmp, matrix);
        }

        return tmp;
    }

    static void solve() {
        int[][] result = power(matrix, B);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

12865번: 평범한 배낭

N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가진다.

최대 K만큼의 무게만 넣을 수 있는 배낭이 있을 때 가지고 갈 수 있는 물건들의 가치의 최댓값을 찾아라

1≤N≤100, 1≤K≤100,000, 1≤W≤100,000, 0≤V≤1,000

단위 무게당 가장 가치있는 물건을 넣어볼까 생각할 수 있다. 하지만 그러면 안 된다. 물건을 쪼갤 수 없을뿐더러 해당 경우가 최선의 경우인지 보장이 안된다.

완전탐색의 경우에는 해당 물건을 넣냐 안넣냐의 경우가 존재해 O(2^100)으로 불가능하다

결국 부분 문제의 해를 이용하는 DP를 써야한다.

dp 배열의 의미부터 정해보자. 물건을 넣냐 안 넣냐 와 무게 이 두 가지가 필요하다.

즉 dp[i][w] = i번 째 물건까지 고려했을 때, 무게 w를 사용해서 얻을 수 있는 최대 가치가 된다.

i 번 째 물건을 넣을 수 있는 경우가 넣을 수 없는 경우가 존재한다.

i번 째 물건을 넣을 수 있는데 넣는 경우와 안 넣는 경우도 존재한다.

i 번 째 물건을 넣을 수 있는 경우는 다음과 같다.

dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])가 된다.

i 번 째 물건을 넣을 수 없는 경우는 다음과 같다.

dp[i][w] = dp[i-1][w]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static class Item {
        int weight;
        int value;

        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    static FastReader scan = new FastReader();
    static int N;
    static int K;
    static Item[] items;

    static void input() {
        N = scan.nextInt();
        K = scan.nextInt();
        items = new Item[N + 1];
        for (int i = 1; i <= N; i++) {
            Item item = new Item(scan.nextInt(), scan.nextInt());
            items[i] = item;
        }
    }

    static void solve() {
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= K; w++) {
                if (items[i].weight <= w) {
                    // 해당 아이템을 넣을 수 있는 경우
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i].weight] + items[i].value);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        System.out.println(dp[N][K]);
    }

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}