프로그래밍

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

www.acmicpc.net/problem/1647

[난이도] Gold4

[유형] 최소 스패닝 트리 (크루스칼)

[풀이]

크루스칼 알고리즘을 이용해 MST를 구하고 그중 가장 큰 edge를 제거하면 cost를 가장 작게하면서 마을을 두개로 나눌 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct eg{
    int c,a,b;
};
vector<eg> v;
int N,M,uf[100001],cnt,ans;
bool cmp(eg& a,eg& b){
    return a.c < b.c;
}
int find(int a){
    if(a==uf[a]) return a;
    return uf[a] = find(uf[a]);
}
bool merge(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa==pb) return 0;
    uf[pa] = find(pb);
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    v.resize(M);
    for(int i=0;i<M;i++){
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=1;i<=N;i++) uf[i] = i;
    for(int i=0;;i++){
        if(merge(v[i].a,v[i].b)){
            if(++cnt==N-1) break;
            ans+=v[i].c;
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/16235

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이] 

우선순위 큐를 사용한 코드는 시간초과가 나서 vector+sort를 조합해서 A/C를 받았다. 나무가 생각보다 많이 만들어질 수 있어서 push,pop 과정에서 시간이 많이 드는 것 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,K;
long long ans;
int dy[8] = {1,-1,0,0,1,1,-1,-1};
int dx[8] = {0,0,1,-1,1,-1,-1,1};
vector<long long> tree[101][101];;
int A[101][101],yb[101][101],seed[101][101];
void feed(int y,int x){
    auto& tr = tree[y][x];
    vector<long long> tt;
    int tyb=0;
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(yb[y][x] >= age){
            yb[y][x]-=age;
            tt.push_back(age+1);
        }else{
            tyb += age/2;
        }        
    }
    tr = tt;
    yb[y][x] += tyb;
}

void expd(int y,int x){
    auto& tr = tree[y][x];
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(age%5==0){
            for(int i=0;i<8;i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N) continue;
                seed[ny][nx]++;
            }   
        }        
    }
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            scanf("%d",&A[i][j]);
            yb[i][j] = 5;
        }
    for(int i=0;i<M;i++){
        int y,x,z;
        scanf("%d%d%d",&x,&y,&z);
        tree[x][y].push_back(z);
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) sort(tree[i][j].begin(),tree[i][j].end());
        
    while(K--){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                feed(i,j);
                seed[i][j]=0;
            }
        }
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) expd(i,j);

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                for(int k=0;k<seed[i][j];k++) tree[i][j].push_back(1);
                sort(tree[i][j].begin(),tree[i][j].end());
                yb[i][j] += A[i][j];
                if(K==0) ans += tree[i][j].size();
            }
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/15685

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이]

시키는대로 하자

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4] = {0,-1,0,1};
int dx[4] = {1,0,-1,0};
int N;
bool map[102][102];
int main(){
    scanf("%d",&N);
    for(int dc=0;dc<N;dc++){
        int x,y,d,g;
        scanf("%d%d%d%d",&x,&y,&d,&g);
        vector<int> seq(1);

        for(int i=0;i<g;i++){
            int sz = seq.size();
            for(int j=sz-1;j>=0;j--) seq.push_back((seq[j]+1)%4);
        }
        map[y][x] = 1;
        for(int v : seq) {
            v=(v+d)%4;
            y+=dy[v];
            x+=dx[v];
            map[y][x] = 1;
        }
    }

    int ans = 0;
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            if(map[i][j]&&map[i+1][j]&&map[i+1][j+1]&&map[i][j+1]) ans++;  
        }
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/14002

[난이도] Gold4

[유형] DP (LIS)

[풀이]

d[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열의 길이

prev[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열에서 i번째 앞의수 위의 두가지를 이용해서 구한다.

#include <cstdio>
int N,a[1001],d[1001],prev[1001];
void prt(int n){
    if(n==0) return;
    prt(prev[n]);
    printf("%d ",a[n]);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=1;i<=N;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]) {
                if(d[i]<d[j]+1){
                   d[i]=d[j]+1;
                   prev[i]=j;
                }
            }
        }
    }
    int mxi=0,mxV=0;
    for(int i=1;i<=N;i++) {
        if(d[i] > mxV){
            mxi=i;
            mxV=d[i];
        }
    }
    printf("%d\n",mxV);
    prt(mxi);
}

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

www.acmicpc.net/problem/13913

[난이도] Gold4

[유형] BFS

[풀이]

최단 경로까지 출력해야 하므로 방문 체크를 할때 어디서 왔는지를 저장 후 답을 찾았을 때 재귀적으로 출력한다.

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int s,e,visit[100001];
void prt(int n){
    if(n==-2) return;
    prt(visit[n]);
    printf("%d ",n);
}
int main(){
    scanf("%d%d",&s,&e);
    memset(visit,-1,sizeof(visit));
    queue<int> q;
    visit[s] = -2;
    q.push(s);
    int cnt = 0;
    while(!q.empty()){
        
        int qsz = q.size();
        while(qsz--){
            int cur = q.front(); q.pop();
            if(cur==e){
                printf("%d\n",cnt);
                prt(cur);
                return 0;
            }

            int nxt;
            if(cur+1<=100000) {
                nxt = cur+1;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }
            if(cur-1>=0) {
                nxt = cur-1;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }
            if(cur*2<=100000) {
                nxt = cur*2;
                if(visit[nxt]==-1){
                    visit[nxt]=cur;
                    q.push(nxt);
                }
            }            
        }
        cnt++;
    }
}

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

www.acmicpc.net/problem/1351

[난이도] Gold4

[유형] DP

[풀이]

dp[n] = dp[n/P]+dp[n/Q]

N 제한이 크므로 map을 이용한다.

#include <cstdio>
#include <map>
using namespace std;
using ll = long long;
ll N;
map<ll,ll> m;
int P,Q;
ll sol(ll n){
    if(n==0) return 1;
    if(m.find(n) != m.end()) return m[n];
    return m[n] = sol(n/P)+sol(n/Q);
}
int main(){
    scanf("%lld%d%d",&N,&P,&Q);
    printf("%lld",sol(N));
}

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

www.acmicpc.net/problem/1339

[난이도] Gold4

[유형] Greedy / 완전탐색

[풀이]

1. Greedy

모든 문자가 1이라고 가정하고 각 문자의 자리수를 고려한 총합이 최대가 되는 문자에 9부터 차례로 할당했을 때의 합을 출력한다.

2. 완전탐색

k가 총 문자 종류의 수일 때 9-k+1 ~ 9 의 문자를 각 문자에 할당할 수 있는 모든 경우의 수를 고려하면 된다. 10!이므로 시간초과나지 않는다. (stoi를 사용했을 경우에 시간초과가 났음)

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int N,a[27],ans,cnt;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<s.size();j++){
            int sz = s.size()-j-1;
            int k = 1;
            while(sz--) k*=10;
            a[s[j]-'A'] += k;
        }
    }
    vector<int> v;
    for(int i=0;i<26;i++) if(a[i]) v.push_back(a[i]);
    sort(v.begin(),v.end());
    int j=0;
    for(int i=9-v.size()+1;i<=9;i++) ans += i*v[j++];
    cout << ans;
}


// #include <algorithm>
// #include <vector>
// #include <string>
// #include <iostream>
// #include <set>
// using namespace std;
// int N,cvt[27],ans;
// vector<string> a;
// int main(){
//     set<char> s;
//     scanf("%d",&N);
//     a.resize(N);
//     for(int i=0;i<N;i++){
//         cin >> a[i];
//         for(auto c : a[i]) s.insert(c);
//     }
//     vector<int> v;
//     for(int i=0;i<s.size();i++) v.push_back(9-i);
//     reverse(v.begin(),v.end());
//     do{ 
//         int i=0;
//         for(auto c : s) {
//             cvt[c-'A']=v[i++];
//         }
//         int sum = 0;
//         for(auto str : a){
//             int k=1;
//             for(int j=str.size()-1;j>=0;j--) {
//                 sum+=cvt[str[j]-'A']*k;
//                 k*=10;
//             }
//         }
//         ans = max(ans,sum);
//     }while(next_permutation(v.begin(),v.end()));
//     cout << ans;
// }

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