프로그래밍

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=583&sw_prbl_sbms_sn=17050

[난이도] level3
[유형] BFS

[풀이]
태범이와 소나기 모두 시간에 따라 1칸씩 움직이기 때문에 태범이의 다음 전진 가능한 위치를 저장하는 q1,
소나기의 위치를 저장하는 q2 두개의 queue를 선언한 뒤 BFS를 돌려주었습니다.
소나기부터 전진시킨 뒤 태범이를 전진시키야 소나기에 의해 범준이의 전진이 막히는지 정확히 파악할 수 있습니다.

#include <cstdio>
#include <queue>
using namespace std;
int R,C,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},ey,ex;
char map[50][50];
bool visit1[50][50],visit2[50][50];
int main(){
    scanf("%d%d",&R,&C);
    queue<pair<int,int>> q1,q2;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='W') {
                visit1[i][j]=1;
                q1.push({i,j});
            }
            else if(map[i][j]=='H') ey=i,ex=j;
            else if(map[i][j]=='*') {
                visit2[i][j]=1;
                q2.push({i,j});
            }
        }
    }
    int ans=0;
    while(!q1.empty()){
        int sz = q2.size();
        while(sz--){
            auto [cy,cx] = q2.front(); q2.pop();  
            for(int k=0;k<4;k++){
                int ny=cy+dy[k],nx=cx+dx[k];
                if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='X'||map[ny][nx]=='H'||visit2[ny][nx]) continue;
                visit2[ny][nx]=1;
                q2.push({ny,nx});
            }
        }
        sz = q1.size();
        while(sz--){
            auto [cy,cx] = q1.front(); q1.pop();  
            if(cy==ey&&cx==ex){
                printf("%d",ans);
                return 0;
            }
            for(int k=0;k<4;k++){
                int ny=cy+dy[k],nx=cx+dx[k];
                if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='X'||visit1[ny][nx]||visit2[ny][nx]) continue;
                visit1[ny][nx]=1;
                q1.push({ny,nx});
            }
        }
        ans++;
    }
    puts("FAIL");
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/GINI야_도와줘.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=582&sw_prbl_sbms_sn=16917

[난이도] level4
[유형] 다익스트라

[풀이]
1에서 출발해서 N까지 도착할때 필요한 최소 레벨을 구하는 문제입니다.
다익스트라를 응용해서 풀 수 있습니다.
일반적인 다익스트라의 경우 [현재 노드 cur 까지 올때까지 필요했던 cost] + [다음 노드 nxt까지 가는데 필요한 cost] 를 더해주어 이 값이 현재 dist[nxt]의 값보다 작다면 이 값으로 dist[nxt]를 업데이트 해주는 방식으로 풀지만
이 문제의 경우 [현재 노드 cur 까지 올때까지 필요한 최소 level]과 [다음 노드 nxt까지 가는데 필요한 level] 의
최댓값과 level[nxt]를 비교해서 업데이트 해주면 됩니다. 왜냐하면 nxt까지 가는데 둘중 더 높은 레벨만큼은 반드시 필요하기 때문입니다.

또한 문제의 조건에 따라 최종노드 N까지 가는데 필요한 level보다 크면서 가장 작은 소수를 구해야 하므로
level[N]보다 큰 첫번째 소수를 구해서 출력해주면 정답이 됩니다.

#include <cstdio>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
using namespace std;
int N,M;
int level[10001];
vector<pair<int,int>> adj[10001];
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        adj[u].push_back({v,c});
        adj[v].push_back({u,c});
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=N;i++) level[i]=1e9;
    pq.push({0,1});
    level[1]=0;

    while(!pq.empty()){
        auto [clv,cur] = pq.top(); pq.pop();
        if(clv!=level[cur]) continue;

        for(auto [nxt,lv] : adj[cur]){
            int nlv = max(lv,clv);
            if(nlv < level[nxt]){
                level[nxt]=nlv;
                pq.push({nlv,nxt});
            }
        }
    }
    for(int i=level[N]+1;;i++){
        bool ok=1;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0) {
                ok=0;
                break;
            }
        }
        if(ok) {
            printf("%lld",i);
            return 0;
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/지우는_소수를_좋아해.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581&sw_prbl_sbms_sn=16912

[난이도] level3
[유형] 시뮬레이션

[풀이]
레일의 최대 개수가 N밖에 안되므로 next_permutation을 이용하면 모든 레일 순서를 구할 수 있습니다.
각 순서마다 문제의 조건에 맞게 시뮬레이션 하면 들어야 하는 무게의 최솟값을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,K,a[10],ans=9e8;
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    do{
        int cur=0, work=0;
        for(int i=0;i<K;i++){
            int r = M;
            while(1){
                r-=a[cur];
                if(r<0) break;
                work+=a[cur++];
                cur%=N;
            }
        }
        ans=min(ans,work);
    }while(next_permutation(a,a+N));
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/택배_마스터_광우.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=413&sw_prbl_sbms_sn=16837

[난이도] level2
[유형] 수학

[풀이]
규칙성을 찾는 문제입니다.
점화식을 만들어보면
A1 = 2 이며
Ak = 2*(Ak-1)+1 이 됩니다.

최종 답은 총 동그라미의 개수이므로 (An)^2을 출력해주면 됩니다.

#include <cstdio>
int N,ans=2;
int main(){
   scanf("%d",&N);
   while(N--) ans = 2*(ans-1)+1;
   printf("%d",ans*ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/지도_자동_구축.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409&sw_prbl_sbms_sn=16804

[난이도] level2
[유형] DFS

[풀이]
전형적인 DFS 문제입니다.
입력을 받을 때 %1d 와 같이 써주면 문제의 입력과 같이 붙어있는 입력에 대해서도 한자리씩 받을 수 있습니다.
블록의 크기를 저장할때는 multiset을 이용하였습니다. 따로 정렬을 해주지 않아도 set은 트리구조이기 때문에
정렬된 상태가 유지되며 저장되기 때문입니다.

#include <cstdio>
#include <set>
using namespace std;
int N,map[25][25],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
bool visit[25][25];
int dfs(int y,int x){
    visit[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=N||!map[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%1d",&map[i][j]);
    multiset<int> ans;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(map[i][j] && !visit[i][j]) ans.insert(dfs(i,j));
    printf("%d\n",ans.size());
    for(auto v : ans) printf("%d\n",v);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/장애물_인식_프로그램.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=408&sw_prbl_sbms_sn=16793

[난이도] level2
[유형] 구현

[풀이]
int형 배열에 저장해서 비교하려면 다소 귀찮기 때문에
string에 입력값을 저장한 뒤 "12345678"이면 ascending, "87654321"이면 descending, 둘다 아니라면 mixed를 출력해주면 됩니다.

#include <string>
#include <iostream>
using namespace std;
string s(8,' ');
int main(){
    for(int i=0;i<8;i++) cin >> s[i];
    if(s=="12345678") cout << "ascending";
    else if(s=="87654321") cout << "descending";
    else cout << "mixed";
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/8단_변속기.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=407&sw_prbl_sbms_sn=16789

[난이도] level2
[유형] 구현

[풀이]
N번 P를 곱할때마다 모듈러 연산을 해주면 됩니다.
계산중 int 범위를 넘어갈 수 있으므로 처음부터 long long으로 자료형을 잡고 하면 편합니다.

#include <cstdio>
using ll = long long;
int N;
ll K,P,mod=1000000007;
int main(){
    scanf("%lld%lld%d",&K,&P,&N);
    while(N--) K=(K*P)%mod;
    printf("%lld",K);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/바이러스.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395

[난이도] level2
[유형] 정렬

[풀이]
무게당 가격이 높은것부터 배낭에 넣으면 됩니다.
pair 배열에 {무게당 가격(Pi),금속의 무게(Mi)} 로 저장한 뒤 정렬하면
무게당 가격의 내림차순으로 정렬이 됩니다.
N-1번 금속부터 거꾸로 금속을 넣을 수 있을만큼 넣어으면서 금속의 가격을 계산해서 더해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,W,ans;
pair<int,int> v[1000000];
int main(){
    scanf("%d%d",&W,&N);
    for(int i=0;i<N;i++){
        int m,p;
        scanf("%d%d",&m,&p);
        v[i]={p,m};
    }
    sort(v,v+N);
    for(int i=N-1;i>=0,W>0;i--){
        int k = min(v[i].second,W);
        W-=k;
        ans+=k*v[i].first;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/금고털이.cpp