프로그래밍

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

[난이도] Gold4
[유형] 브루트포스

[풀이]
map이 5x5이므로 전부 해보자는 생각으로 모든 케이스를 직접 구했다.
(1,1)에서 사과가 있는 (y,x)로 조건을 만족하며 갈 수 있는 모든 경로에 대해서
(y,x)에서 다시 (5,5)로 갈 수 있는 모든 경로중에 조건을 만족하는 케이스를 모두 더하면 된다.
조건 : (1,1)->(y,x) , (y,x)->(5,5) 의 거리가 같아야하며, 모든 사과가 있는 칸을 지나야함.

(간단한 풀이)
(1,1)에서 (y,x)까지 갈 수 있는 모든 경우의 수가 정답.

#include <cstdio>
int ans,K,a[6][6],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int sol2(int y,int x,int c,int t){
    if(y==5&&x==5) return c==t && c+t==24-K;
    int ret =0;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<1||nx<1||ny>5||nx>5||a[ny][nx]) continue;
        a[ny][nx]=1;
        ret+=sol2(ny,nx,c+1,t);
        a[ny][nx]=0;
    }
    return ret;
}
void sol(int y,int x,int c){
    int v = sol2(y,x,0,c);
    ans+=v;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<1||nx<1||ny>5||nx>5||a[ny][nx]) continue;
        a[ny][nx]=1;
        sol(ny,nx,c+1);
        a[ny][nx]=0;
    }
}
int main(){
    scanf("%d",&K);
    for(int i=0;i<K;i++){
        int y,x;
        scanf("%d%d",&y,&x);
        a[y][x]=1;
    }
    a[1][1]=1;
    sol(1,1,0);
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] 브루트포스

[풀이]
에라토스테네스의 체를 이용해 0~9999999 까지의 소수를 기록해놓고
만들 수 있는 모든 숫자를 브루트포스를 이용해 구한 뒤 소수이면 set에 저장한다.
이 set의 크기가 정답이다.

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
bool prime[10000000];
int t;
int main(){
    ios_base::sync_with_stdio();
    cin.tie();
    cout.tie();
    cin >> t;
    prime[0]=prime[1]=1;
    for(int i=2;i<10000000;i++){
        for(int j=i*2;j<10000000;j+=i){
            prime[j]=1;
        }
    }
    while(t--){
        string s;
        cin >> s;
        int n = s.size();
        set<int> st;
        for(int i=1;i<(1<<n);i++){
            string a;
            for(int j=0;j<n;j++){
                if((i&(1<<j))>0) a.push_back(s[j]);
            }
            
            sort(a.begin(),a.end());
            
            do{
                int num = stoi(a);
                if(!prime[num]) st.insert(num);
            }while(next_permutation(a.begin(),a.end()));
        }
        cout << st.size();
    }
}

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

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

[난이도] Gold3
[유형] 브루트포스

[풀이]
아래 재귀함수를 이용하여 모든 케이스를 확인해준다.
sol(int c1,int c2,int r,int k0,int k1,int k2);
변수:
c1 : 경희가 내야할 손동작의 현재 index
c2 : 민호가 내야할 손동작의 현재 index
r : 이번 게임에 참가 못하는 사람의 index (0:지우, 1:경희, 2:민호)
k0 : 지우가 현재까지 이긴 횟수
k1 : 경희가 현재까지 이긴 횟수
k2 : 민호가 현재까지 이긴 횟수

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

#include <cstdio>
int N,K,map[10][10],seq[3][21];
bool use[10];
int sol(int c1,int c2,int r,int k0,int k1,int k2){
    if(k1==K||k2==K) return 0;
    if(k0==K) return 1;
    int a=-1,b;
    for(int i=0;i<3;i++){
        if(r!=i){
            if(a==-1) a=i;
            else b=i;
        }
    }
    int ka,kb,t;
    if(b==1) t=c1;
    else t=c2;
    kb=seq[b][t];
    if(a!=0){
        ka=seq[a][c1];
        if(map[ka][kb] < 2) {
            if(sol(c1+1,c2+1,a,k0,k1,k2+1)) return 1;
        }else{
            if(sol(c1+1,c2+1,b,k0,k1+1,k2)) return 1;
        }
    }else{
        for(int i=1;i<=N;i++){
            if(!use[i]){
                use[i]=1;
                int kk1=k1,kk2=k2,cc1=c1,cc2=c2;
                if(b==1) kk1++, cc1++;
                else kk2++, cc2++;
                                
                if(map[i][kb]<2){
                    if(sol(cc1,cc2,a,k0,kk1,kk2)) return 1;
                }else{
                    if(sol(cc1,cc2,b,k0+1,k1,k2)) return 1;
                }
                use[i]=0;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    for(int i=1;i<3;i++) 
        for(int j=0;j<20;j++) scanf("%d",&seq[i][j]);
    printf("%d",sol(0,0,2,0,0,0));
}

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

[난이도] Gold4
[유형] 브루트포스

[풀이]
문제를 선택할 수 있는 모든 경우에 대해서 문제에 주어진 조언이 만족되는지를 확인하면 된다.
완전탐색은 비트마스크를 이용해서 구현하였다.

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

#include <cstdio>
#include <algorithm>
using namespace std;
int N,L,R,X,a[15],ans;
int main(){
    scanf("%d%d%d%d",&N,&L,&R,&X);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=1;i<(1<<N);i++){
        int ml=2e9,mr=0,sum=0,cnt=0;
        for(int j=0;j<N;j++){
            if((i&(1<<j))>0){
                mr=max(mr,a[j]);
                ml=min(ml,a[j]);
                sum+=a[j];
                cnt++;
            }
        }
        if(cnt>=2 && sum<=R&&sum>=L&&mr-ml>=X) ans++;
    }
    printf("%d",ans);
}

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

[난이도] Gold4
[유형] 브루트포스

[풀이]
N이 10^4라서 2차원 배열에 체크해놓고 뭘 할려고 하면 시간초과가 난다.

제한이 10^2인 L,M (그물의 둘레,고기들의 개수) 를 기준으로 문제를 풀어가야 한다.
모든 고기 i를 확인하면서 그 고기를 그물 끝에 걸리게 하는 모든 그물을 만들어서
i+1~M번째 고기들이 그물 안에 들어올 수 있는지를 확인하면 된다.

주의할점이 그물을 만들 때 i번 고기가 꼭지점에만 오도록 하면 안되고
좌우로 움직여주면서 i번 고기가 그물 끝에 걸릴 수 있는 모든 그물에 대해서
확인을 해줘야 한다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,L,M,ans;
pair<int,int> v[10000];
int main(){
    scanf("%d%d%d",&N,&L,&M);
    for(int i=0;i<M;i++) scanf("%d%d",&v[i].first,&v[i].second);
    sort(v,v+M);
    for(int h=1;h<L/2;h++){
        int w = L/2-h;
        if(w>N-1||h>N-1) continue;
        for(int i=0;i<M;i++){
            int y = v[i].first,x=v[i].second;
            for(int k=0;k<=w;k++){
                int cnt=1;
                for(int j=i+1;j<M;j++){
                    int ny = v[j].first, nx=v[j].second;
                    if(ny>y+h) break;
                    if(x-k<=nx&&nx<=x-k+w) cnt++;      
                }
                ans = max(ans,cnt);
            }
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/17281

[난이도] Gold4

[유형] Brute force, Simulation

[풀이] 

next_permutation을 이용해 모든 경우를 다 해보면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,a[50][9],res;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<9;j++) scanf("%d",&a[i][j]);
    
    vector<int> p = {1,2,3,4,5,6,7,8};
    do{
        vector<int> seq = p;
        seq.insert(seq.begin()+3,0);
        int scr = 0,j=0;
        for(int i=0;i<N;i++){
            vector<bool> pos(3);
            int out=0;
            while(out<3){
                int cmd = a[i][seq[j]];
                if(cmd==0) out++;
                else if(cmd<4){
                    for(int k=2;k>=0;k--){
                        if(pos[k]==1) {
                            int nxt = k+cmd;
                            if(nxt > 2) scr++;
                            else pos[nxt] = 1;
                            pos[k]=0;
                        }     
                    }
                    pos[cmd-1]=1;
                }else {
                    for(int k=2;k>=0;k--){
                        scr+=pos[k];
                        pos[k]=0;
                    }
                    scr++;
                }
                j=(j+1)%9;
            }
        }
        res = max(res,scr);
    }while(next_permutation(p.begin(),p.end()));
    printf("%d",res);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17281.cpp

www.acmicpc.net/problem/17135

[난이도] Gold4

[유형] 시뮬레이션, Brute Force

[풀이]

각 열의 성에서 먼 순서대로 stack에 쌓아서 시뮬레이션하면 편하게 풀수 있다.

#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
int N,M,D,ans,tt,total;
int dist(int sx,int ey,int ex){
    return ey+abs(ex-sx);
}
void fwd(vector<stack<int>>& s){
    for(int i=0;i<s.size();i++){
        stack<int> tmp;
        while(!s[i].empty()){
            tmp.push(s[i].top()-1); 
            s[i].pop();
        }
        while(!tmp.empty()){
            int t = tmp.top(); tmp.pop();
            if(t>0) s[i].push(t);
            else tt--;
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&M,&D);
    vector<stack<int>> st(M);
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            int v;
            scanf("%d",&v);
            if(v) {
                st[j].push(N-i+1); 
                total++;
            }
        }
    }
    vector<bool> seq(M);
    for(int i=M-3;i<M;i++) seq[i]=1;
    do{
        vector<int> a;
        for(int i=0;i<seq.size();i++) if(seq[i]) a.push_back(i);

        auto cpst = st;
        int cnt = 0;
        tt = total;
        while(1){
            set<int> rmv;
            for(auto sx : a){
                int mxidx = -1, minv = 1<<9;
                for(int x=0;x<M;x++){
                    if(cpst[x].empty()) continue;
                    int ey = cpst[x].top();
                    int d = dist(sx,ey,x);
                    if(d>D) continue;
                    if(minv > d){
                        mxidx = x;
                        minv = d;
                    }
                }
                if(mxidx!=-1) rmv.insert(mxidx);
            }
            for(auto r : rmv){
                cpst[r].pop();
                cnt++;
                tt--;
            }
            fwd(cpst);
            if(tt==0) break;
        }
        ans = max(ans,cnt);
    }while(next_permutation(seq.begin(),seq.end()));
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17135.cpp