📚 문제

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N=5이고 동전이 각각 3원, 2원, 1원, 9원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 

또 다른 예시로, N=3이고 동전이 각각 3원, 5원, 7원짜리라고 가정합시다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1<=N<=1,000)

둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다. 이때 각 화폐 단위는 1,000,000 이하의 자연수입니다.

📝 문제 해결

동전에 대한 정보가 주어졌을 때, 화폐 단위를 기준으로 오름차순 정렬한다. 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인하면 된다.

1부터 target-1까지의 모든 금액을 만들 수 있다고 가정해보자. 화폐 단위가 작은 순서대로 동전을 확인하며, 현재 확인하는 동전을 이용해 target 금액 또한 만들 수 있는지 확인하면 된다. 만약 target 금액을 만들 수 있다면, target 값을 증가시키면 된다.

1. 처음에는 금액 1을 만들 수 있는지 확인하기 위해, target = 1로 설정한다.
2. target = 1을 만족할 수 있는지 확인한다. 화폐 단위가 1인 동전으로 금액 1을 만들 수 있다. -> target = 1 + 1 = 2로 업데이트한다.
3. target = 2를 만족할 수 있는지 확인한다. 화폐 단위가 2인 동전이 있다. -> target = 2 + 2 = 4로 업데이트한다.
4. target = 4를 만족할 수 있는지 확인한다. 화폐 단위가 3인 동전이 있다. -> target = 4 + 3 = 7로 업데이트한다.
5. target = 7을 만족할 수 있느닞 확인한다. 이보다 큰 화폐 단위 8인 동전이 있으므로 따라서 금액 7을 만드는 방법은 없다. 따라서 정답은 7이 된다.

이러한 원리를 이용하면 단순히 1) 동전을 화폐 단위 기준으로 정렬한 뒤에, 2) 화폐 단위가 작은 동전부터 하나씩 확인하면서 3) target 변수를 업데이트하는 방법으로 최적의 해를 계산할 수 있다.

💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        int target = 1;
        for (int i = 0; i < n; i++) {
            if (target < arrayList.get(i)) break;
            target += arrayList.get(i);
        }

        System.out.println(target);
    }
}

📚 문제

nxm 크기의 금광이 있다. 금광은 1x1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오.

만약 다음과 같이 3x4 크기의 금광이 존재한다고 가정한다면,

(2,1) -> (3,2) -> (3,3) -> (3,4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다.

첫째 줄에 테스트 케이스 T가 입력된다. (1<=T<=1000)

매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력된다. (1<=n,m<=20)

둘째 줄에 nxm개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (1<=금의 개수<=100)

📝 문제 해결

테이블 정의

arr[][]: 초기 금광 정보를 담는 테이블

dp[][] : 최대 금의 크기를 저장하는 테이블

점화식 찾기

• 왼쪽 위에서 오는 경우
• 왼쪽 아래에서 오는 경우
• 왼쪽에서 오는 경우

이 3가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주면 된다.

 dp[i][j] = arr[i][j] + Math.max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

💻 코드

package dynamicProgramming;

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

public class dp04 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[][] arr = new int[20][20];
        int[][] dp = new int[20][20];

        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    dp[i][j] = arr[i][j];
                }
            }

            for (int j = 1; j < m; j++) {
                for (int i = 0; i < n; i++) {
                    int leftUp, leftDown, left;
                    if (i == 0) leftUp = 0;
                    else leftUp = dp[i - 1][j - 1];
                    if (i == n - 1) leftDown = 0;
                    else leftDown = dp[i + 1][j - 1];
                    left = dp[i][j - 1];
                    dp[i][j] = dp[i][j] + Math.max(leftUp, Math.max(leftDown, left));
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++) {
                max = Math.max(max, dp[i][m - 1]);
            }
            System.out.println(max);
        }
    }
}

플로이드 위셜 알고리즘이란? '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용

플로이드 위셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다.
(모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문)
노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하여 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍으로 볼 수 있다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다.
ex) 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다.
알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1 개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한다.
이후에 A -> 1번 노드 -> B로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다.

구체적인 (K번의 단계에 대한) 점화식은 다음과 같다.

따라서 전체적으로 3중 반복문을 이용하여 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.
('A에서 B로 가는 최소 비용' 과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신)
즉, '바로 이동하는 거리'가 '특정한 노드를 거쳐서 이동하는 거리'보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신

시간 복잡도 : O(N^3)

(노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려)

플로이드 위셜 알고리즘 소스 코드

package graph;

import java.util.*;

public class graph03 {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값 설정(연결되지 않은 간선)
    public static int n, m; // 노드의 개수(n), 간선의 개수(m)
    public static int[][] graph = new int[501][501];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<501; i++){
            Arrays.fill(graph[i], INF); // 최단 거리 테이블 모두 무한으로 초기화
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) graph[i][j] = 0; // 자기 자신으로 가는 비용 0으로 초기화
            }
        }

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph[a][b] = c;
        }

        // 점화식에 따라 플로이드 위셜 알고리즘 수행
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    graph[j][k] = Math.min(graph[j][k], graph[j][i]+graph[i][k]);
                }
            }
        }

        // 수행된 결과를 출력
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(graph[i][j] == INF) System.out.print("INFINITY ");
                else System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

📚 실전문제

방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하려 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 이 때, 다른회사로 이동하기 위한 시간은 정확히 1만큼의 시간이 소요된다.

또한 오늘 A씨는 소개팅에도 참여해야 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 물건을 팔러 가기 이전에 소개팅 상대의 회사에 가서 함께 커피를 마실 예정이다. 따라서 A씨는 1번 회사에서 출발해 K번 회사를 거쳐 X번 회사로 가는 것이 목표다. 이 때 A씨는 가장 빠르게 이동하려고 한다. A씨가 이동하게 되는 최소 시간을 계산하는 프로그램을 작성해라. 이 때 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다.

예를 들어 N=5, X=4, K=5이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.

(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), (3번, 5번), (4번,5번)

이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1 - 3 - 5 -4)로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간을 이동할 수 있다.
따라서 이 경우 최소 이동 시간은 3이다.

📝 문제 해설

1번 노드에서 X(소개팅)를 거쳐 K(방문판매 회사)로 가는 최단 거리 = 1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리

💻 코드 

package graph;

import java.util.Arrays;
import java.util.Scanner;

public class graph04 {
    public static final int INF = (int) 1e9;
    public static int n, m, x, k;
    public static int[][] graph = new int[101][101];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<101; i++){
            Arrays.fill(graph[i], INF); // 최단 거리 테이블 모두 무한으로 초기화
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) graph[i][j] = 0; // 자기 자신으로 가는 비용 0으로 초기화
            }
        }

        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        x = sc.nextInt(); // 방문해야하는 회사 위치
        k = sc.nextInt(); // 소개팅 참석 회사 위치

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    graph[j][k] = Math.min(graph[j][k], graph[j][i]+graph[i][k]);
                }
            }
        }

        int distance = graph[1][k] + graph[k][x];

        if(distance >= INF) System.out.println(-1);
        else System.out.println(distance);
    }
}

📚 문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.

정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요.

• 첫째 줄에 집의 수 N(1<=N<=200,000)과 도로의 수 M(N-1<=M<=200,000)이 주어집니다.
• 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며 공백으로 구분합니다. ( X번 집과 Y번 집 사이에 양방향 도로의 길이가 Z라는 의미)

📝 문제 해결

이 문제에서는 가로등이 켜진 도로만을 이용해서 모든 두 집이 서로 도달이 가능해야 한다는 조건을 제시하고 있음.

이때 최소한의 비용으로 모든 집을 연결해야 하기 때문에 최소 신장 트리로 해결할 수 있음. 따라서 주어진 입력을 통해서 그래프를 구성한 뒤에 크루스칼 알고리즘을 수행하면 된다.

이 문제처럼 '왕래'할 수 있다는 것은 그래프에서 각 노드가 서로 연결되어 있다는 의미로 최소 신장 트리를 의심해봐야 함.

💻 코드

import java.util.*;

class Edge implements Comparable<Edge> {

    private int distance;
    private int nodeA;
    private int nodeB;

    public Edge(int distance, int nodeA, int nodeB) {
        this.distance = distance;
        this.nodeA = nodeA;
        this.nodeB = nodeB;
    }

    public int getDistance() {
        return this.distance;
    }

    public int getNodeA() {
        return this.nodeA;
    }

    public int getNodeB() {
        return this.nodeB;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Edge other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

public class Main {

    // 노드의 개수와 간선의 개수
    public static int n, m;
    public static int[] parent = new int[200001]; // 부모 테이블 초기화하기
    // 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
    public static ArrayList<Edge> edges = new ArrayList<>();
    public static int result = 0;

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        // 모든 간선에 대한 정보를 입력 받기
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            edges.add(new Edge(z, x, y));
        }

        // 간선을 비용순으로 정렬
        Collections.sort(edges);
        int total = 0; // 전체 가로등 비용

        // 간선을 하나씩 확인하며
        for (int i = 0; i < edges.size(); i++) {
            int cost = edges.get(i).getDistance();
            int a = edges.get(i).getNodeA();
            int b = edges.get(i).getNodeB();
            total += cost;
            // 사이클이 발생하지 않는 경우에만 집합에 포함
            if (findParent(a) != findParent(b)) {
                unionParent(a, b);
                result += cost;
            }
        }
        // 절약할 수 있는 최대 금액 = 전체 가로등을 켜는 비용 - 최소 신장 트리를 구성하는 비용
        System.out.println(total - result);
    }
}