[백준] 25048번: 랜선 연결 Java

문제

최근 연구실 위치를 옮긴 은규와 연구실 사람들은 큰 난관에 봉착했습니다. 그것은 바로 이사한 연구실에 인터넷이 연결되지 않는다는 것입니다!

다행히도 이웃 연구실에서 인터넷이 연결된 랜선 한 가닥을 얻을 수 있었고, 이 랜선을 연구실에 있는 스위치에 잘 연결해서 인터넷을 연결할 수 있게 되었습니다.

현재 연구실에는 N개의 스위치(Network Switch)와 M개의 컴퓨터가 있습니다. 각 스위치는 a_i개의 포트가 있고 b_i의 설치 비용이 듭니다. 스위치에서 컴퓨터로 인터넷을 공급하기 위해서는 1개의 인터넷이 공급된 선이 연결되어야 하며 (a_i)−1개의 다른 기기(스위치 혹은 컴퓨터)에 인터넷을 공급할 수 있습니다. 스위치끼리 사이클을 형성하는 것은, 화재의 위험이 있기 때문에 불가능합니다.

은규는 깔끔한 연결을 좋아하기 때문에 스위치에 남는 포트가 없도록 연결하려고 합니다. 또 은규는 효율성도 중요시하기 때문에 가능한 여러 연결 방식이 존재한다면 그중 가장 적은 비용을 사용하는 방식을 택해서 모든 컴퓨터에 인터넷이 공급되도록 할 것입니다. 이러한 연결이 가능하다면 가능한 연결의 최소 비용을 출력하고, 불가능하다면 -1을 출력합니다.

 

입력

첫 번째 줄에 스위치의 개수를 의미하는 정수 N (1≤N≤300)이 주어집니다.

두 번째 줄부터 N+1 번째 줄에는 각 줄마다 정수 a_i (2≤ai≤10^5)와 b_i (0≤bi≤10^9)가 공백으로 구분되어 주어집니다. 각각 i 번째 스위치의 포트 개수와 설치 비용을 의미합니다.

 N+2 번째 줄에는 연결할 컴퓨터의 개수 M (1≤M≤10^5)이 주어집니다.

 

출력

첫 번째 줄에 조건을 만족하는 연결 방식 중 최소 비용을 출력합니다. 그러한 연결 방식이 없다면 -1을 출력합니다.

 

https://www.acmicpc.net/problem/25048

25048번: 랜선 연결

접근

다이나믹 프로그래밍을 이용하여 해결 할 수 있습니다.

스위치들을 비용이 적은순, 포트 개수가 적은 순으로 정렬하고,

행을 스위치 번호로, 열을 연결한 컴퓨터 개수를 하는 dp 테이블을 잡고

배낭문제처럼 1행부터 시작하여 순차적으로 진행합니다.

 

만약 포트 개수가 a개이고, 비용이 b인 i번째 스위치를 x개의 컴퓨터를 연결하는 경우,

먼저 i-1번째 스위치에 y대의 컴퓨터가 연결되어 있다고 가정합니다.

i-1번째 스위치에서 컴퓨터 한대와의 연결을 해제하고, i번째 스위치와 인터넷 공급선을 연결합니다. (y-1)

i번째 스위치는 하나의 공급선과 연결되었음으로, a-1만큼 컴퓨터를 공급할 수 있습니다. (a-1)

따라서 (a-1) + (y-1) = x 이며

y = x -a +2 입니다.

 

그럼 x개의 컴퓨터를 i 스위치를 이용한 연결 비용은 어떻게 될까요?

(i-1 스위치의 x-a+2 개의 비용) + (i 스위치 설치 비용) 이 들 것입니다.

이를 dp로 표현하자면 dp[i-1][x-a+2] + b 가 됩니다.

 

우리가 문제에서 구하고자 하는 값은 최소값임으로

i번째 스위치를 사용하여 x개의 컴퓨터를 연결하는 비용 (dp[i-1][x-a+2] + b)

vs i번째 스위치를 사용하지 않고 x개의 컴퓨터를 연결하는 비용 (dp[i-1][x]) 

중 적은 값을 취합니다.

 

처음에 랜선 공급선 1개가 주어졌음으로 dp[0][1]=0 이며 dp의 나머지 값은 최대값으로 설정해줍니다.

dp[스위치수][컴퓨터수] 까지 연산을 하고,

이 값이 최대값이면 -1, 아닐 경우 이 값을 최종적으로 리턴합니다.

 

구현

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

public class Main {
	//https://www.acmicpc.net/problem/25048
	//최대 비용
	static final long INF = Long.MAX_VALUE/3;
	//스위치 클래스
	static class Swich implements Comparable<Swich>{
		int portCount;
		long cost;
		public Swich(int portCount , long cost) {
			this.portCount= portCount;
			this.cost = cost;
		}
		//정렬, 1) 비용이 적은 순, 2) 포트 수가 적은 순 
		@Override
		public int compareTo(Swich o) {
			if(this.cost<o.cost) return -1;
			else if(this.cost>o.cost) return 1;
			else {
				if(this.portCount<o.portCount) return -1;
				else if(this.portCount>o.portCount) return 1;
				return 0;
			}
		}
	}
	
	public static long getMinCost(List<Swich> list, int swichs, int computers) {
		//리스트 정렬
		Collections.sort(list);
		//다이나믹 프로그래밍을 위한 배열 선언
		long[][] dp = new long[swichs+1][computers+1];
		//배열 값 INF로 초기화
		for(int i=0;i<swichs+1;i++) {
			for(int j=0;j<computers+1;j++) {
				dp[i][j]=INF;
			}
		}
		//스위치 0개에는 컴퓨터 1개만 사용 가능
		dp[0][1]=0;
		//연결한 스위치 번호
		for(int i=1;i<=swichs;i++) {
			Swich swich = list.get(i-1);
			//연결한 컴퓨터 수
			for(int j=1;j<=computers;j++) {
				//이전 스위치의 연결한 컴퓨터 수 -1(인터넷 공급을 위한 선)
				//+  현재 스위치의 포트 수 -1(인터넷 공급을 위한 선) = j
				//=> 이전 스위치의 연결한 컴퓨터 수 = j - 현재 스위치의 포트 수 +2
				//j - 현재 스위치의 포트 수 +2가 범위 내에 있고,
				//현재 스위치 설치가 더 이득이면 업데이트
				if(j-swich.portCount+2>=0
						&&j-swich.portCount+2<=computers
						&&dp[i-1][j]>dp[i-1][j-swich.portCount+2]+swich.cost) {
					dp[i][j]=dp[i-1][j-swich.portCount+1]+swich.cost;
				//아닐 시 이전 스위치 비용과 같음
				}else {
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		//INF면 -1, 아니면 값 출력
		return dp[swichs][computers]==INF?-1:dp[swichs][computers];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//스위치 개수
		int n = Integer.parseInt(br.readLine());
		//스위치 정보를 저장할 리스트
		List<Swich> list = new ArrayList<>();
		StringTokenizer st;
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			int portCount=Integer.parseInt(st.nextToken()); //포트 수
			int cost=Integer.parseInt(st.nextToken()); //비용
			list.add(new Swich(portCount, cost)); //스위치 정보 추가
		}
		//컴퓨터 개수
		int m = Integer.parseInt(br.readLine());
		System.out.println(getMinCost(list, n, m));
		br.close();
	}
}