프로그래밍

www.acmicpc.net/problem/17404

[난이도] Gold4

[유형] DP

[풀이]

마지막 집은 첫번째 집과 색이 달라야 하므로 첫번째 집의 색을 기억해야 한다. 첫번째 집의 색을 R,G,B각각 고정했을 때의 비용의 최솟값중 가장 작은 것이 정답이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,cost[1000][3],dp[1000][3],INF=1e9;
int ans=INF;
int sol(int s){
    for(int i=0;i<N;i++) for(int j=0;j<3;j++) dp[i][j] = INF;
    dp[0][s] = cost[0][s];
    int ret = INF;
    for(int i=1;i<N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j!=k) dp[i][j] = min(dp[i][j],dp[i-1][k]+cost[i][j]);
            }
        }
    }
    for(int i=0;i<3;i++) if(i!=s) ret = min(ret,dp[N-1][i]);
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) 
        for(int j=0;j<3;j++) scanf("%d",&cost[i][j]);
    for(int i=0;i<3;i++){
        int ret = sol(i);
        ans = min(ans,ret);
    }
    printf("%d",ans);
}

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

www.acmicpc.net/problem/17298

[난이도] Gold4

[유형] Stack

[풀이]

1. 스택이 비어있으면 index push

2. 스택에 원소가 있을때 현재 값보다 작은 원소들은 NGE가 현재 값으로 정하고 pop

#include <cstdio>
#include <stack>
using namespace std;
int N,a[1000000],nge[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d",&a[i]);
        nge[i]=-1;
    }
    stack<int> st;
    for(int i=0;i<N;i++){
        while(!st.empty() && a[i] > a[st.top()]) {
            nge[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for(int i=0;i<N;i++) printf("%d ",nge[i]);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17298.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/1715

[난이도] Gold4

[유형] 우선순위큐

[풀이]

가장 작은 것부터 두개씩 뽑고, 두개의 합을 다시 큐에 넣으면 된다.

#include <cstdio>
#include <queue>
using namespace std;
int main(){
    priority_queue<int> pq;
    int N,a,ret=0;
    scanf("%d",&N);
    while(N--) scanf("%d",&a), pq.push(-a);
    while(pq.size()>1){
        int u,v;
        u=pq.top(); pq.pop();
        v=pq.top(); pq.pop();
        ret+=-u-v;
        pq.push(u+v);
    }
    printf("%d",ret);
}

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

www.acmicpc.net/problem/17140

[난이도] Gold4

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

[풀이]

R 연산에 대한 함수만 정의하고 배열을 반시계 방향으로 회전하는 함수를 들어서 이용하면 C 연산은 따로 정의하지 않아도 해결할 수 있다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using vvi = vector<vector<int>>;
int r,c,k;

vvi rot(vvi& m){
    int csz = m.size();
    int rsz = m[0].size();
    vector<vector<int>> ret(rsz,vector<int>(csz));
    for(int i=0;i<rsz;i++)
        for(int j=0;j<csz;j++) ret[i][j] = m[j][rsz-i-1];

    return ret;
}

vvi R(vvi& m){
    vvi tmp;
    int mxl = 0;
    for(auto v : m){
        map<int,int> cntMap;
        for(auto i : v) {
            if(i!=0) cntMap[i]++;
        }

        vector<pair<int,int>> ov;
        for(auto p : cntMap){
            ov.push_back({p.second,p.first});
        }
        sort(ov.begin(),ov.end());
        vector<int> res;
        for(auto o : ov){
            res.push_back(o.second);
            res.push_back(o.first);
        }
        mxl = max(mxl,(int)res.size());
        tmp.push_back(res);
    }
    mxl = min(100,mxl);
    for(auto& t : tmp) t.resize(mxl);
    return tmp;
}

int main(){
    scanf("%d%d%d",&r,&c,&k);
    r--,c--;
    vvi map;
    for(int i=0;i<3;i++){
        vector<int> a(3);
        for(int j=0;j<3;j++) scanf("%d",&a[j]);
        map.push_back(a);
    }
    int time = 0;
    while(1){
        int rsz = map.size();
        int csz = map[0].size();
        if(r < rsz && c < csz && map[r][c]==k) break;
        if(time==100){
            time = -1;
            break;
        }
        if(rsz >= csz){
            map = R(map);
        }else{
            map = rot(map);
            map = R(map);
            for(int i=0;i<3;i++) map=rot(map);
        }
        time++;
    }
    printf("%d",time);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17140.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

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