241115 최근 풀이
풀이 전략
: 문제를 읽어보고, 순열도 가능하고, 백트래킹도 가능하다는 판단을 함.
그런데 간단하게 순열로 하는게 낫다고 판단해서 순열로 Go!
pair와 순열에 대해서
: pair의 first 값이 동일하다면 pair<int,int> 를 next_permutation 불가하다. 그래서 chicken.size() 에 맞게 check 불변수를 만듦.
그리고 m개 갯수에 맞게 check 에닥 true를 지정함.
그리고 check 를 next_permutation 을 하게 되면 check에 넣은 true 값들이 이리 저리 순서가 변경된다.
만약에 chicken 집이 5개 라고 하고, 2개를 선택한다고 하면
check[0] = true, chekc[1] = true 이고, next_permutation 하면
어쨋든 왔다 갔다 하면 check 5개 중에서 반드시 2개는 true라는 점이다.
이를 이용해서 next_permutation 처리하자.
기준에 대해서
: 우리가 구하고자 하는 치킨거리이고, 치킨집 중에서 m개를 선택해서 m개에 대한 모든 house에 대해서 최소값의 누적합이 치킨거리라고 할 수 있다.
1) 즉 house가 기준이 되어야 할까????
2) 치킨집 중에서 선택받은 m개가 기준이 되어야 할까????
- 생각해보기
: 5개인 2 중에서 2개를 고르는 거다.
1인 house의 입장에서 치킨집 마다의 dist 비용이 다르고, 가장 작은 dist를 구하는 것이기 때문에 2중 포문 작성시 house가 위로 올라가야 한다.
-> 기준은 house가 되어야 한다. m이 1이라고 할 때 ,
빨간색 집을 기준으로 생각해보면, 치킨거리는 오른쪽 상단에 있는 0,1 치킨집이 최고의 효율을 자랑한다.
--> 코드로는 대충 이런식으로 생각할 수 있다.
for(int i ~~ house.size())
{
비교 하는 변수
for(int 치킨집 중에서 m개 까지 선택 )
{
dist 값을 구하고,
}
min( ~~ )
}
240330 풀이 그리고 잘못된 부분.
전략
: 치킨집 , 집을 vector<pair<int,int>> 로 만들어 놓은 다음에
전체 집 vs 치킨 집중에서 m만큼을 뽑아서 거리비용이 최소값을
추출하려고 했다.
- 치킨 집중에서 m만큼을 get하는 것이니까. next_permutation을
생각했다.
놓친점
- 1.next_pertutation 하기 전에 sort를 놓침.
- sort를 하기 전에 치킨집은 vector<pair<int,int>> 이다.
따라서 vector 변수 만들어서 이걸로 next_permu 처리 해야 했다.
- sort를 하기 전에 치킨집은 vector<pair<int,int>> 이다.
최근 코드
- 0909 20:06 ~ 20:38 조합으로 품
http://boj.kr/11693a38461a42bc9570af6609ad589d
변경한 부분
: 최소값 처리할 부분을 굉장히 크게 잡아야 함.
250으로 했다가 틀림...
풀이전략
: 치킨집 중에서 m의 갯수만큼을 temp로 넣어줌.
temp vs 모든 집 을 비교하면서 가장 최단거리의 합을 구하는 문제임/
-> 치킨집 중에서 m개만큼을 추출하는 것이므로, 조합 문제임.
알아야 할점.
조합이라서 next_permutation에 pair 값을 넣어서 돌리면 안됨...
-> 시간 초과 발생함.
--> 왜냐하면 3번째 인자가 compare 함수인데, 비교 정책을 만들지 않았기 때문임.
https://velog.io/@kwt0124/%EC%88%9C%EC%97%B4
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>>v(n, vector<int>(n));
vector<pair<int, int>>chicken;
vector<pair<int, int>>home;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> v[i][j];
if (v[i][j] == 2)
chicken.push_back(make_pair(i, j));
if (v[i][j] == 1)
home.push_back(make_pair(i, j));
}
}
// next_permutation 하기 위한 사전 작업
sort(chicken.begin(), chicken.end());
int res = 1000000;
do
{
int sum = 0;
//for (int j = 0; j < home.size(); ++j)
{
//chicken[j].second << endl;
// 선택된 치킨 집과 모든 집과의 최소거리를 구하자.
//int mmmin = 1000000;
// 한개의 집을 기준으로해서 치킵집 원소와의 거리를 비교해서
// 최소값을 뽑아야 함.
for (int i = 0; i < m; ++i)
{
//int dist = abs(chicken[i].first - home[j].first)
// + abs(chicken[i].second - home[j].second);
//mmmin = min(dist, mmmin);
cout << chicken[i].first << " " << chicken[i].second << endl;
}
//sum += mmmin;
}
//cout << sum << endl;
cout << "hello" << endl;
// 합산 해야 함.
//res = min(res, sum);
} while (next_permutation(chicken.begin(), chicken.end()));
//cout << "last result : ";
cout << res;
}주의할 점.
- 결과
-> pair<int,int>로는 정렬 안됨. compare 함수를 정의하기 않앗기 때문임.
--> 1차원 배열을 만들고, 그것을 조합하고,
---> check와 chicken을 동기화하면서 처리하자.5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
0 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
1 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
2 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
3 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
4 1
hello
코드
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>>v(n, vector<int>(n));
vector<pair<int, int>>chicken;
vector<pair<int, int>>home;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> v[i][j];
if (v[i][j] == 2)
chicken.push_back(make_pair(i, j));
if (v[i][j] == 1)
home.push_back(make_pair(i, j));
}
}
vector<bool>check(chicken.size());
for (int i = 0; i < m; ++i)
check[i] = true;
// next_permutation 하기 위한 사전 작업
sort(check.begin(), check.end());
int res = 1000000;
do
{
int sum = 0;
for (int j = 0; j < home.size(); ++j)
{
//chicken[j].second << endl;
// 선택된 치킨 집과 모든 집과의 최소거리를 구하자.
int mmmin = 1000000;
// 한개의 집을 기준으로해서 치킵집 원소와의 거리를 비교해서
// 최소값을 뽑아야 함.
// 조합되는 것은 체크 인덱스 임.
// 따라서 체크 인덱스와 치킨 인덱스를 동일시하는 방식으로
// 진행 하기 위해서
for (int i = 0; i < check.size(); ++i)
//for (int i = 0; i < m; ++i)
{
if (check[i] == false)
continue;
int dist = abs(chicken[i].first - home[j].first)
+ abs(chicken[i].second - home[j].second);
mmmin = min(dist, mmmin);
//cout << chicken[i].first << " " << chicken[i].second << endl;
}
sum += mmmin;
}
//cout << "hello" << endl;
// 합산 해야 함.
res = min(res, sum);
} while (next_permutation(check.begin(), check.end()));
//cout << "last result : ";
cout << res;
}
