백준 15686 <치킨 배달>

이 문제도 마찬가지로 조합을 구할 수 있냐 하는 문제인 것 같다.

치킨집이 최대 13개이기때문에 최대 13 C m 이 될 것이고 이 값은 1만이 넘지 않는다.

집의 개수는 최대 2 * N 개가 넘지 않으니 최대 100개 이므로 집에서 치킨집까지의 모든 거리를 계산해도 천만? 정도가 될 것이다.

 

이 문제는 이전 문제와 다르게 접근을 해보았는데 visit배열을 이용해서 방문을 체크해주고 방문한 경우에는 num+1을 해서 재귀를 해주도록 하였다.

 

이 문제에서 주의해야 할 점은 최대 M개를 고르는 문제라고 하여 그 이하의 경우도 생각해주어야 하는가? 였다.

답은 당연히 No!이다.

 

우리가 구하는 것은 집에서 가장 가까운 치킨집을 고르는 것이기 때문에 치킨집의 개수는 많을수록 좋다.

 

 

그다음은 각각의 집에 대해 가까운 치킨집의 거리를 계산해 그합들의 최솟값을 결정해 주면 되는 문제였다.

 

문제를 접근할 때 문제를 잘 이해하는 것이 중요하다 라는 것을 다시 한번 느낀 문제이다.

 

전체 코드

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

public class Main {

	public static class whkvy{
		int x;
		int y;
		public whkvy(int x,int y) {
			this.x=x;
			this.y=y;
		}
	}
	static ArrayList<whkvy> wlq=new ArrayList<whkvy>(),clzlsa=new ArrayList<whkvy>();
	static int visit[];
	static int map[][];
	static int N,M,min;
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner kb=new Scanner(System.in);
		N=kb.nextInt();
		map=new int[N][N];
		M=kb.nextInt();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j]=kb.nextInt();
				if(map[i][j]==1)
					wlq.add(new whkvy(i,j));
				else if(map[i][j]==2)
					clzlsa.add(new whkvy(i,j));
			}
		}
		visit=new int[clzlsa.size()];
		min=100000000;
		start(0,0);
		System.out.println(min);
	}
	public static void start(int k,int num) {
		if(num==M) {
			dist();
			return;
		}
		if(k>=clzlsa.size())
			return;
		visit[k]=1;
		start(k+1,num+1);
		visit[k]=0;
		start(k+1,num);
	}
	public static void dist(){
		int re=0;
		for(int i=0;i<wlq.size();i++) {
			int k=100000000;
			for(int j=0;j<clzlsa.size();j++) {
				if(visit[j]==1) {
					k=Math.min(k, Math.abs(wlq.get(i).x-clzlsa.get(j).x)+ 
                               Math.abs(wlq.get(i).y-clzlsa.get(j).y));
				}
			}
			re+=k;
		}
		if(min>re)
			min=re;
	}

}