프로그래밍

www.acmicpc.net/problem/19238

[난이도] Gold4

[유형] BFS, Simulation (삼성SW기출)

[풀이] 

1. y시작,x시작,y종료,x종료,현재 택시위치에서의 거리 d 이 5가지를 저장하는
구조체 P를 정의한다.
2. vector<P> s를 정의 M개의 P를 저장한다.
3. M회 루프를 돌면서 매 시행마다 s를 정렬해준다. 정렬은 comparator 를
   재정의하는 방식으로 한다. 거리,y좌표,x 우선순위로 정렬하면 항상
   s[0]이 지금 태우러 가야하는 사람이다. 뽑은 뒤 s[0]은 필요없으므로
   벡터에서 지워준다.
4. 벽에 의해 택시로 도달할 수 없는 사람이 있는 겨우와, 연료를 다쓰는 경우를
   예외처리 해준다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
    int y,x,ey,ex,d;
};
vector<P> s;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int N,M,K,map[21][21],py,px,INF=9e8;
bool visit[21][21];
int bfs(int y,int x){
    memset(visit,0,sizeof(visit));
    queue<P> q;
    q.push({y,x});
    visit[y][x] = 1;
    int ret = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            P qf = q.front(); q.pop();
            if(qf.y==py&&qf.x==px) return ret;
            for(int i=0;i<4;i++){
                int ny = qf.y+dy[i];
                int nx = qf.x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N || map[ny][nx]) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx] = 1;
                }
            }
        }
        ret++;
    }
    return INF;
}
bool cmp(P& a,P& b){
    if(a.d < b.d) return 1;
    else if(a.d==b.d){
        if(a.y<b.y) return 1;
        else if(a.y==b.y) return a.x < b.x;
        return 0;
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    s.resize(M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    
    scanf("%d%d",&py,&px);
    for(int i=0;i<M;i++) scanf("%d%d%d%d",&s[i].y,&s[i].x,&s[i].ey,&s[i].ex);

    for(int i=0;i<M;i++){
        for(int j=0;j<s.size();j++) s[j].d = bfs(s[j].y,s[j].x);    
        sort(s.begin(),s.end(),cmp);
        P t = s[0];
        s.erase(s.begin());
        if(K-t.d < 0) {
            K=-1;
            break;
        }
        K-=t.d, py=t.y, px=t.x;

        int nDist = bfs(t.ey,t.ex);
        if(K-nDist < 0){
            K=-1;
            break;
        }
        py=t.ey, px=t.ex;
        K+=nDist;
    }
    printf("%d",K);
}

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

www.acmicpc.net/problem/1918

[난이도] Gold4

[유형] 스택 (중위표기법 -> 후위표기법)

[풀이] 스택 (중위표기법 -> 후위표기법)

연산자 우선순위와 Stack을 이용. 연산자의 우선순위는 ( < -,+ < /,* : )는 Stack에 들어가지 않으므로 정의하지 않는다. 문자열을 순회하면서

1. 피연산자면 바로 출력

2. '('이면 스택에 push

3. ')'이면 여는 괄호가 나올때까지 스택의 원소를 팝하면서 출력

4. Stack이 비어있거나 Stack의 top보다 우선순위가 낮아질때까지 Stack의 top을 pop하면서 출력 후 push ('('인 경우 2에서 예외로 무조건 push)

4번에서 while문을 통해 반복해주는 것이 중요.

#include <stack>
#include <iostream>
#include <cctype>
#include <string>
using namespace std;
string a,ret;
int p(char c){
    if(c=='(') return 0;
    if(c=='+'||c=='-') return 1;
    return 2;
}
int main(){
    cin >> a;
    stack<char> s; 
    for(char c : a){
        if(isalpha(c)) ret+=c;
        else if(c=='(') s.push(c);
        else if(c==')'){
            while(1){
                char op = s.top(); s.pop();
                if(op=='(') break;
                ret+=op;
            }
        }
        else{
            while(!s.empty() && p(s.top()) >= p(c)) {
                ret+=s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    while(!s.empty()) {
        ret+=s.top();
        s.pop();
    }
    cout << ret;
} 

github.com/has2/Problem-Solving/commit/f60ec108a19e4d6d59156a99880d7e222b1a3f26

www.acmicpc.net/problem/17779

[난이도] Gold4

[유형] Brute force, DFS (삼성SW기출)

[풀이]

1. 문제의 주어진 조건에 따라 5선거구의 경계를 체크한다.

2. (1,1)은 1선거구, (1,N)은 2선거구, (N,1)은 3선거구 (N,N)은 4선거구에 각각 무조건 포함되므로 4개의 점에서 DFS를 수행하면서 각 선거구의 인구를 구한다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N,map[21][21],A[21][21],total,ans=1e8;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool check(int d1,int d2,int x,int y){
    bool r = d1 >= 1 && d2 >= 1 && 1 <= x && x < x+d1+d2 && x+d1+d2 <= N;
    bool c = 1 <= y-d1 && y-d1 < y && y < y+d2 && y+d2 <=N;
    return r&&c;
}
void mask(int d1,int d2,int x,int y){
    int sx,sy,dx,dy;

    sx=x,sy=y,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x,sy=y,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }
    sx=x+d1,sy=y-d1,dx=1,dy=1;
    for(int i=0;i<=d2;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }  
    sx=x+d2,sy=y+d2,dx=1,dy=-1;
    for(int i=0;i<=d1;i++) {
        map[sx][sy] = 1;
        sx+=dx,sy+=dy;
    }     
}

int dfs(int d1,int d2,int x,int y,int r,int c,int k){
    if(k==1){
        if(!(1<=r&&r<x+d1&&1<=c&&c<=y)) return 0;
    }else if(k==2){
        if(!(1<=r&&r<=x+d2&&y<c&&c<=N)) return 0;
    }else if(k==3){
        if(!(x+d1<=r&&r<=N&&1<=c&&c<y-d1+d2)) return 0;
    }else if(k==4){
        if(!(x+d2<r&&r<=N&&y-d1+d2<=c&&c<=N)) return 0;
    }
    map[r][c] = k;
    int ret = A[r][c];
    for(int i=0;i<4;i++){
        int nr = r+dx[i];
        int nc = c+dy[i];
        if(nr < 1 || nc < 1 || nr > N || nc > N || map[nr][nc]) continue; 
        ret += dfs(d1,d2,x,y,nr,nc,k);
    }
    return ret;
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            scanf("%d",&A[i][j]);
            total+=A[i][j];
        }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int d1=1;d1<=N;d1++){
                for(int d2=1;d2<=N;d2++){
                    if(!check(d1,d2,i,j)) continue;
                    memset(map,0,sizeof(map));
                    mask(d1,d2,i,j);
                    int sx = 1,sy=1;
                    vector<int> sum;
                    sum.push_back(dfs(d1,d2,i,j,1,1,1));
                    sum.push_back(dfs(d1,d2,i,j,1,N,2));
                    sum.push_back(dfs(d1,d2,i,j,N,1,3));
                    sum.push_back(dfs(d1,d2,i,j,N,N,4));
                    int rm = total;
                    for(int i=0;i<4;i++) rm -= sum[i];
                    sum.push_back(rm);
                    sort(sum.begin(),sum.end());
                    ans = min(ans,sum.back()-sum.front());
                }
            }
        }
    }    
    printf("%d",ans);
}

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

www.acmicpc.net/problem/17406

[난이도] Gold4

[유형] 시뮬레이션

[풀이]

next_permutation을 이용해 모든 경우의 수를 다해본다. permutation으로 돌아가는것은 index라는 것에 주의.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,K,org[51][51],cp[51][51],tmp[51][51],r[6],c[6],s[6],v[6],inf=1e8;
int sol(){
    int ret = inf;
    for(int i=0;i<K;i++){
        int ll = 2*s[v[i]]+1, yy = r[v[i]]-s[v[i]], xx = c[v[i]]-s[v[i]];        
        int l = ll, y = yy, x = xx;
        while(l>0){
            if(l==1) {
                tmp[y][x] = cp[y][x];
                break;
            }
            for(int j=x+1;j<x+l;j++) tmp[y][j] = cp[y][j-1];
            for(int j=y+1;j<y+l;j++) tmp[j][x+l-1] = cp[j-1][x+l-1];
            for(int j=x;j<x+l-1;j++) tmp[y+l-1][j] = cp[y+l-1][j+1];
            for(int j=y;j<y+l-1;j++) tmp[j][x] = cp[j+1][x];
            y++,x++;
            l-=2;
        }
        for(int j=yy;j<yy+ll;j++)
            for(int k=xx;k<xx+ll;k++) cp[j][k] = tmp[j][k];
    }
    for(int i=1;i<=N;i++){
        int sum = 0;
        for(int j=1;j<=M;j++) sum+=cp[i][j];
        ret = min(ret,sum);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++) 
        for(int j=1;j<=M;j++) scanf("%d",&org[i][j]);

    for(int i=0;i<K;i++) {
        scanf("%d%d%d",&r[i],&c[i],&s[i]);
        v[i] = i;
    }
    int ans = inf;
    do{
        for(int i=1;i<=N;i++) copy(org[i],org[i]+M+1,cp[i]);
        ans =min(ans,sol());
    }while(next_permutation(v,v+K));
    printf("%d",ans);
} 

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

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/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