[코테연습] 연구 분배하기

https://level.goorm.io/exam/351828/%EC%97%B0%EA%B5%AC-%EB%B6%84%EB%B0%B0%ED%95%98%EA%B8%B0/quiz/1

구름LEVEL

 

문제 타입

• 문자열 변환 문제
• 매칭 상태를 효율적으로 계산하는 최적화 문제
• 비트 연산과 다이나믹 프로그래밍을 결합한 문제

---

문제 분석

1. 문제의 핵심:
   • 주어진 연구원과 연구소 매칭 비용 행렬에서 최소 비용으로 모든 연구원을 연구소에 배치.
   • 각 연구원은 정확히 하나의 연구소에 배치되어야 하고, 각 연구소는 하나의 연구원만 배치받을 수 있음.
2. 해결 방법의 주요 특징:
   • 매칭 상태를 비트마스크로 표현.
     • 각 비트가 연구소의 매칭 여부를 나타냄.
     • 예: "011"은 두 개의 연구소가 이미 매칭된 상태를 의미.
   • 다이나믹 프로그래밍을 사용해 최소 비용을 점진적으로 계산.
3. 다이나믹 프로그래밍 상태 정의:
   • dp 배열은 각 매칭 상태에서 최소 비용을 저장.
   • dp[상태]는 "현재 매칭된 상태"에서의 최소 비용.
   • 예: dp[001]은 첫 번째 연구소만 매칭된 상태에서의 최소 비용을 의미.
4. 상태 전이:
   • 연구원을 아직 매칭되지 않은 연구소에 배치하면서 새로운 상태를 계산.
   • dp[새로운 상태] = 최소 비용(dp[현재 상태] + 현재 연구원의 비용).
5. 결과 계산:
   • 모든 연구소가 매칭된 상태에서 최소 비용을 반환.

---

문제 풀이

1. 입력과 초기화:
   • 비용 행렬을 입력받고 dp 배열을 초기화.
   • 초기 상태 dp[0]은 매칭되지 않은 상태의 비용을 0으로 설정.
   • 나머지 상태는 무한대 값으로 초기화.
2. 상태 전이:
   • 가능한 모든 매칭 상태를 탐색.
   • 현재 매칭 상태에서, 매칭되지 않은 연구소를 선택하여 새로운 상태를 계산.
   • dp 배열을 갱신하며 최소 비용을 계산.
3. 최종 결과 반환:
   • 모든 연구소가 매칭된 상태에서 최소 비용(dp[모든 상태])을 반환.

 

 

--------------------------

 

문제 예제

입력

2
1 3
7 2

첫 번째 줄: 연구원과 연구소의 수는 2.
두 번째 줄: 첫 번째 연구원이 연구소에 배치될 때의 비용 행렬 (1 3).
세 번째 줄: 두 번째 연구원이 연구소에 배치될 때의 비용 행렬 (7 2).

---

비용 행렬

1 3
7 2

연구원 0이 연구소 0에 배치될 때 비용은 1, 연구소 1에 배치될 때 비용은 3.
연구원 1이 연구소 0에 배치될 때 비용은 7, 연구소 1에 배치될 때 비용은 2.

---

알고리즘의 동작 과정

초기 상태

동적 계획법을 위한 배열 dp 초기화:
dp[0] = 0 (아무 연구소도 매칭되지 않은 상태의 비용은 0).
dp[1], dp[2], dp[3]은 매우 큰 값으로 초기화 (매칭되지 않은 상태).

---

상태 전이

1. 첫 번째 상태: dp[0] (아무 연구소도 매칭되지 않은 상태)
   연구원 0이 연구소에 배치될 차례.
   가능한 연구소:
   • 연구소 0:
     새로운 상태는 dp[1].
     dp[1] = 최소값(dp[1], dp[0] + 비용[0][0]).
     결과: dp[1] = 최소값(큰 값, 0 + 1) = 1.
   • 연구소 1:
     새로운 상태는 dp[2].
     dp[2] = 최소값(dp[2], dp[0] + 비용[0][1]).
     결과: dp[2] = 최소값(큰 값, 0 + 3) = 3.
   업데이트된 dp 배열:
   dp = [0, 1, 3, 큰 값]
2. 두 번째 상태: dp[1] (연구소 0이 매칭된 상태)
   연구원 1이 연구소에 배치될 차례.
   가능한 연구소:
   • 연구소 1:
     새로운 상태는 dp[3].
     dp[3] = 최소값(dp[3], dp[1] + 비용[1][1]).
     결과: dp[3] = 최소값(큰 값, 1 + 2) = 3.
   업데이트된 dp 배열:
   dp = [0, 1, 3, 3]
3. 세 번째 상태: dp[2] (연구소 1이 매칭된 상태)
   연구원 1이 연구소에 배치될 차례.
   가능한 연구소:
   • 연구소 0:
     새로운 상태는 dp[3].
     dp[3] = 최소값(dp[3], dp[2] + 비용[1][0]).
     결과: dp[3] = 최소값(3, 3 + 7) = 3.
   최종 dp 배열:
   dp = [0, 1, 3, 3]

---

최종 결과

모든 연구소가 매칭된 상태 dp[3]에서 최소 비용은 3.

---

출력

3

---

과정 요약

• dp 배열은 연구소의 매칭 상태를 나타내며, 매칭되지 않은 상태에서 매칭된 상태로 전환하며 최소 비용을 계산.
• 모든 연구소가 매칭된 상태 dp[3]에서 최종 최소 비용을 반환.
• 결과적으로 최소 비용은 3.

 

 

- java

 

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] arr = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                cost[i][j] = Integer.parseInt(arr[j]);
            }
        }

        int result = minCost(cost, N);
        System.out.println(result);
    }

    static int minCost(int[][] cost, int N) {
        int[] dp = new int[1 << N];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << N); mask++) {
            int researcher = Integer.bitCount(mask); // 현재까지 매칭된 연구원의 수
            for (int j = 0; j < N; j++) {
                // 연구소 j가 이미 매칭된 상태라면 건너뛰기
                if ((mask & (1 << j)) != 0) continue;

                // 새로운 상태
                int newMask = mask | (1 << j);
                dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[researcher][j]);
            }
        }

        return dp[(1 << N) - 1];
    }
}