프로그래밍

https://programmers.co.kr/learn/courses/30/lessons/92343

[난이도] level3
[유형] 완전탐색

[풀이]
총 노드의 개수가 최대 17개밖에 되지 않기 때문에 방문할 수 있는 모든 경우의 수를 다해봐도 문제 해결이 가능합니다.

void sol(int n,set<int> s,int a,int b) 이라는 재귀함수를 만들어서 아래와 같이 정의하였습니다.
n : 현재 방문한 노드,
s : 다음에 방문할 수 있는 노드,
a : 현재 같이있는 양의 수,
b : 현재 같이있는 늑대의 수

현재 방문한 노드의 자식 노드들을 s에 추가해준 줍니다.
그러면 이제 s에 들어있는 노드들은 다음에 방문할 수 있는 모든 노드가 들어있게 됩니다.
s에 들어있는 노드들을 순차적으로 방문하는 재귀함수를 호출해주면서 a , b 값을 누적해가면
최댓값을 구할 수 있습니다.

#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,ans;
vector<int> adj[17],info;
void sol(int n,set<int> s,int a,int b){
    if(info[n]) b++;
    else a++;
    if(b>=a) return;
    s.erase(n);
    ans=max(a,ans);
    for(auto nxt : adj[n]) s.insert(nxt); 
    for(auto v : s) sol(v,s,a,b);
}
int solution(vector<int> _info, vector<vector<int>> edges) {
    N=info.size();
    info=_info;
    for(auto eg : edges) adj[eg[0]].push_back(eg[1]);
    sol(0,{0},0,0);
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/양과_늑대.cpp

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

[난이도] Gold4
[유형] DP,Bitmask,완전탐색

[풀이]
next_permutation으로 푸니까 TLE로 틀려서 Bitmask DP로 풀었다.
선수 11명, 포지션 11개밖에 안되므로 DP[11][1<11] 배열로
11x2^11 O(22528) 안에 해결이 가능하다.

next_permutation이 아닌 재귀를 활용한 완전탐색으로도 0인 경우에 가지치기를 해주면
시간내에 해결이 가능하다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,a[11][11],dp[11][1<<11],inf=-9e8;
int sol(int n,int msk){
    if(n==11) return 0;
    int& ret = dp[n][msk];
    if(ret!=-1) return ret;
    ret = inf;
    for(int i=0;i<11;i++){
        if(((1<<i)&msk)==0 && a[i][n]){
            ret = max(ret,sol(n+1,msk|(1<<i))+a[i][n]);
        }
    }
    return ret;
}
int main(){ 
    scanf("%d",&tc);
    while(tc--){
        for(int i=0;i<11;i++)
            for(int j=0;j<11;j++) scanf("%d",&a[i][j]);       
        memset(dp,-1,sizeof(dp));
        printf("%d\n",sol(0,0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3980.cpp

www.acmicpc.net/problem/1007

[난이도] Gold2

[유형] 완전탐색

[풀이]

N이 20이기 때문에 임의로 N/2, N/2 그룹으로 나누어서 푼다

20C10의 경우의 수 중에 최솟값을 찾으면 된다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,x[20],y[20];
long long xsum[2],ysum[2];
double ans;
bool a[20];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d%d",&x[i],&y[i]);
        memset(a,0,sizeof(a));
        for(int i=N/2;i<N;i++) a[i]=1;
        
        ans = -1;
        do{
            ysum[0]=ysum[1]=xsum[0]=xsum[1]=0;
            for(int i=0;i<N;i++) {
                xsum[a[i]]+=x[i];
                ysum[a[i]]+=y[i];
            }
            double tmp = sqrt((xsum[0]-xsum[1])*(xsum[0]-xsum[1])+(ysum[0]-ysum[1])*(ysum[0]-ysum[1]));
            if(ans < 0 || ans > tmp) ans = tmp;
        }while(next_permutation(a,a+N));
        printf("%f\n",ans);
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1007.cpp

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

[풀이] 완전탐색,부분합

1. n,m 제한이 1000이므로 모든 연속된 구간의 합 sum을 계산한다.

2. sum이 어떤 구간에 있는지는 중요하지 않고 몇개나 나올 수 있는지가 중요하므로

   Acnt,Bcnt 배열을 각각 만들에 sum이라는 값이 몇번 나올 수 있는지를 저장한다.

3. 1,2 과정은 피자 A와 B에 대해 중복되는 연산이므로 func 함수를 만들어서 중복코드를 줄인다.

4. func에서 sum을 구할 때 i를 구간의 크기로 잡는 피자 조각이 n개라면 1에서 n까지 돌아야 한다.

   j는 시작 index로 정한다. 최초 index 0부터 시작하는 i 구간만큼의 sum을 구한다.

   그 뒤의 for문은 j를 옮겨가면서 앞에는 빼주고 뒤에는 더해주는 과정이다.

   i가 최대 크기인 경우엔 이 과정은 break.

5. A,B 한개의 피자에서만 조각을 모두 가져올 수도 있으므로 func에서 sum을 구하는 도중에 답을 더해준다. 

6. Acnt,Bcnt를 모두 구했으면 곱연산으로 경우의 수를 구한다.

https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2632.cpp