[BOJ 25048] 백준 25048번 - 랜선 연결
| 2022 DGIST 현풍전산배 알고리즘 대회 풀이 | ||
|---|---|---|
| A | [BOJ 25044] 에어컨 | |
| B | [BOJ 25045] 비즈마켓 | |
| C | [BOJ 25046] 사각형 게임 (Small) | |
| D | [BOJ 25047] 사각형 게임 (Large) | |
| E | [BOJ 25048] 랜선 연결 | |
| F | [BOJ 25049] 뮤직 플레이리스트 |
1. 문제
$25048$. 랜선 연결 (2022 DGIST 현풍전산배 알고리즘 대회 E번)
2. 풀이
($S$=switch, $C$=computer, $M$=computer 총 개수)
그림1은 $M=4$인 회로이다. 여기에 $a_i=4$인 스위치 하나를 가져다 붙이면, 그림2처럼 $M=6$이 된다. 기존의 회로에서 $C$ 대신 $S$가 하나 붙어서 $C$의 개수가 하나 줄어들고, 대신 새로 붙이는 스위치에 $a_i-1$개만큼 $C$를 더 붙일 수 있게 되기 때문에, $C$의 총 개수가 $a_i-2$개만큼 증가하는 것이다. 이는 어떤 모양의 스위치 트리 회로의 어떤 곳에 새로운 스위치를 가져다 붙이든 동일하다.
각 스위치에 $a_i$개의 포트가 있고, 스위치 설치 비용 $b_i$가 있을 때, $M$개의 컴퓨터를 연결시키는 최소 설치 비용을 구하는 문제이다. 포트 개수와 설치 비용을 각각 weight와 cost로 생각하면, 특정 weight($M$)을 만족시키는 최소 설치 cost를 구하는 문제로 바꾸어 생각할 수 있다. 따라서 knapsack 문제로 간주할 수 있다.
dp[0] = 0;
for(int i = 0; i < N; i++) {
for(int j = M - (port[i] - 2); j >= 1; j--) {
dp[j + (port[i] - 2)] = min(dp[j + (port[i] - 2)], dp[j] + cost[i]);
}
}
단, 예외적으로 처음 랜선에 스위치를 연결하는 경우는 컴퓨터가 $a_i-2$개 증가하는 것이 아니라, $a_i-1$개 증가한다. 따라서, 위의 코드에서 $j=0$인 경우는 따로 처리를 해주어야 하기 때문에, $1\leq j$와 같이 범위가 설정된 것이다. 아래 코드는 처음 랜선에 스위치를 연결하는 경우이다.
for(int i = 0; i < N; i++) {
if (port[i] - 1 <= M) {
dp[port[i] - 1] = min(dp[port[i] - 1], cost[i]);
}
}
이때 주의해야할 점이 있다. knapsack 문제는 하나의 객체에 대해서 모든 발생할 수 있는 경우를 전부 처리하여 dp 배열에 담고, 다음 객체를 지금까지 만들어진 dp 배열에 대입하여 똑같은 작업을 반복한다. 따라서, 위의 두 코드를 한 for문 안에서 처리하지 않고 분리하거나, 두 코드의 순서가 바뀌어버리면, 에러가 발생하게 된다.
또 다른 예외로는 처음 랜선에 바로 컴퓨터를 연결하는 경우가 있다. 스위치를 사용하지 않기 때문에 최소 비용 $0$으로 하나의 컴퓨터를 연결시킬 수 있다. 따라서 $M=1$인 경우는 $0$을 출력하게 해야 한다.
if (M == 1) {
cout << 0;
}
3. 채점 결과
4. 회고
여러 유형의 knapsack 문제에 익숙하지 않으면, 구현하는데 꽤나 어려웠을 것 같은 문제였다.
랜선에 바로 컴퓨터를 연결하는 예외케이스를 찾지 못해, WA를 벗어나기 힘들었다.
댓글남기기