[D-13] 비슷한 유형 #2 (최대 몇 개를 고를 때..)

// BOJ 15686 치킨 배달

#include<cstdio>

#include<vector>

#include<cmath>

#include<algorithm>

#define INF 2e9 

// 인트형에서 최솟값 구할때 이렇게 하면 좋음

using namespace std;

int n, m, ans = INF;

int t, lenH, lenC;

vector<pair<int, int>> hou, chi;

int dist(pair<int, int> a, pair<int, int> b){ return abs(a.first - b.first) + abs(a.second - b.second);}

 

void Init()

{

// 조합류의 문제에서는 별도로 2차원 배열을 선언할 필요가 없는거 같다.

scanf("%d %d", &n, &m);

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

scanf("%d", &t);

if (t == 1) hou.push_back({ i,j });

else if (t == 2) chi.push_back({ i,j });

}

}

}

void simulation()

{

lenH = hou.size();

lenC = chi.size();

vector<int> p(lenC, 1);

for (int i = 0; i < m; i++) p[i] = 0;

// for (int i = 0; i < p.size(); i++) {

// printf("%d", p[i]);

// }

do {

int sum = 0;

for (int i = 0; i < lenH; i++) {

int minV = INF;

for (int j = 0; j < lenC; j++) {

if (p[j] == 0) minV = min(minV, dist(hou[i], chi[j]));

}

sum += minV;

}

ans = min(ans, sum);

} while (next_permutation(p.begin(), p.end()));

}

int main()

{

Init();

simulation();

printf("%d", ans);

return 0;

}

 

// BOJ 14888 연산자 끼워넣기

<코드>

#include<cstdio>

#include<vector>

#include<algorithm>

// +,-,x,/

using namespace std;

 

int n, k;

int maxV = -2e9, minV = 2e9;

int arr[20];

vector<int> op;

 

void Init()

{

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d", &arr[i]);

}

for (int j = 0; j < 4; j++) {

scanf("%d", &k);

while (k--) op.push_back(j);

}

// 0 0 1 2 3 

}

void simulation()

{

do {

int sum = arr[0];

for (int i = 0; i < n - 1; i++)

{

if (op[i] == 0) sum += arr[i+1];

else if (op[i] == 1) sum -= arr[i + 1];

else if (op[i] == 2) sum *= arr[i + 1];

else if (op[i] == 3) sum /= arr[i + 1];

}

maxV = max(sum, maxV);

minV = min(sum, minV);

} while (next_permutation(op.begin(), op.end()));

}

int main()

{

Init();

simulation();

printf("%d\n%d\n", maxV, minV);

return 0;

}