[코딩테스트 스터디/C++] 백준 15686번 치킨배달

1.문제 링크

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

2. 풀이 전 계획과 생각

• 모든 입력을 받기

  for(int i=0;i<n;i++){
    for(int j=0; j<n; j++){
        cin>>v[i][j];
    }
  }
  

• 모든 경우의 수 구현해보기

3. 풀이

#include<iostream>
#include<vector>
#include<algorithm> // min함수 사용  

#define INF 2147483647 // int형 최대 범위 수  

using namespace std;

int n,m;
int homeCnt=0, chickenCnt=0;

vector<pair<int, int> > home;
vector<pair<int, int> > chicken;

// 정수n의 2진수 1비트 개수 반환   
int count_OneBits(int n){
	int cnt_OneBit = 0;
	while(n){
		if(n&1) ++cnt_OneBit;
		n = n >> 1;
	}
	return cnt_OneBit;
}

// 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력
int get_distMinimum(){
	int distMinimum = INF;
	for(int set=0; set<1<<chickenCnt; set++){
		if(count_OneBits(set)==m){
			int sum=0;
			for(int i=0; i<homeCnt; i++){
				int dist = INF;
				for(int j=0; j<chickenCnt; j++){
					if(set&1<<j){
						dist = min(dist, 
						abs(home[i].first-chicken[j].first)+abs(home[i].second-chicken[j].second));
					}
				}
				sum += dist; 
			}
			distMinimum = min(distMinimum, sum);
		}
	}
	return distMinimum;
}

int main(){
	// 입출력 빨라지게 해줌. 
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    
	// 입력
	cin>>n>>m;

	// 입력 
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			int temp; cin>>temp;
			if(temp==1) {
				home.push_back({i,j});
				homeCnt++;	
			}
			else if(temp==2){
				chicken.push_back({i,j});
				chickenCnt++;	
			} 
		}
	}
	
	// 답 출력  
	int ans = get_distMinimum();
	cout<<ans;
}

4. 풀이하면서 고민했던 점

• 모든 경우의 수를 다 구현하면 시간복잡도 조건을 충족 못 시킬까봐 고민함

• 각 경우의 수, 조합을 어떤식으로 표현하고 구현할지 고민함

5. 문제를 풀고 알게된 개념 및 소감

• 모든 입력을 저장할 필요 없다 N*N 배열 형태로 입력이 주어질 때 무조건 모든 입력값을 이중배열에 저장할 필요없다는 것을 알게됨.

• 비트연산 비트연산을 자세히 알게됨.

• 경우의수, 조합 경우의 수와 조합을 이진수 형태로 표현, 구현할 수 있다.