프로그래밍

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

[난이도] level3
[유형] 부분합

[풀이]
구간의 합만 알면 평균을 구할 수 있기 때문에 부분합 배열을 이용하면 됩니다.

#include <cstdio>
#include <cmath>
using namespace std;
int N,K,sum[1000001];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i]=sum[i-1]+v;
    }
    while(K--){
        int a,b;
        scanf("%d%d",&a,&b);
        double ans = (double)(sum[b]-sum[a-1])/(b-a+1);
        ans=ceil(ans*100)/100;
        printf("%.2f\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/성적_평균.cpp

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

[난이도] level3
[유형] Greedy

[풀이]
로봇과 부품의 index를 각각 저장한 뒤,
앞쪽 로봇부터 부품을 할당할때 가능하면 앞쪽 부품을 할당하는 것이 가장 유리합니다.
이를 위해 부품의 index는 queue에 저장해서 앞쪽 부터 순차적으로 꺼내면서 사용해주면 됩니다.

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int N,K;
vector<int> p;
queue<int> q;
string s;
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) {
        char c;
        scanf(" %c",&c);
        if(c=='P') p.push_back(i);
        else q.push(i);
    }
    int ans=0;
    for(auto r : p){
        while(!q.empty()){
            int i = q.front(); 
            if(abs(r-i)<=K) {
                ans++;
                q.pop();
                break;
            }else if(r>i) q.pop();
            else break;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/스마트_물류.cpp

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

[난이도] level3
[유형] 백트래킹

[풀이]
먼저 파악해야 할 것이 로봇은 '#' 로 표시된 점 이외에는 절대로 방문하지 않고
한붓그리기 처럼 '#' 점을 한방에 방문해야 합니다.
로봇이 두칸씩 전진하고, 사용한 명령어를 저장해야 하기 때문에 BFS 혹은 DFS 푸는 것은 어렵다고 판단하여
백트래킹을 이용하였습니다.

'#'인 점만 방문하고, 두칸씩 전진함에 따라 많은 경로가 제외되기 때문에 시간내에 해결이 가능합니다.

커맨드를 최소로 하기 위해 어느 점에서 시작해야 최적인지
'#'인 모든 점에 대해 모든 4방향을 시작점으로 백트래킹을 돌려봐야 합니다.

백트래킹 함수 void sol(int y,int x,int d,int cnt,string cmd)
에서 d는 방향, cnt는 현재까지 방문한 '#' 개수, cmd는 현재까지 사용한 커맨드 string입니다.

어떤 점에 도착했을 때 할 수 있는 전진은 총 4가지 입니다.
좌측으로 회전 뒤 전진("LA")
좌측으로 두번 회전 뒤 전진("LLA")
우측으로 한번 회전 뒤 전진("RA") <- ("LLLA)와 같지만 연산 횟수가 역방향으로 돌리는 "RA"가 더 적습니다.
현재 방향으로 전진 ("A")

위 4가지 케이스에 대해 백트래킹 함수를 다시 호출해주면 됩니다.

#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int H,W,ansd,ansy,ansx,sd,sy,sx;
char map[27][27];
bool visit[27][27];
vector<pair<int,int>> cand;
string ret="-1";

void sol(int y,int x,int d,int cnt,string cmd){

    if(cand.size()==cnt){
        if(ret=="-1" || cmd.size() < ret.size()){
            ret=cmd;
            ansy=sy,ansx=sx,ansd=sd;
            ansd=sd;
        }
        return;
    }

    for(int i=0;i<4;i++){
        int nd=(d+i)%4;
        string nxt="A";
        if(i==1) nxt="LA";
        else if(i==2) nxt="LLA";
        else if(i==3) nxt="RA";

        int ny1=y+dy[nd], nx1=x+dx[nd];
        int ny2=y+2*dy[nd], nx2=x+2*dx[nd];

        if(ny2<1||nx2<1||ny2>H||nx2>W) continue;
        if(map[ny1][nx1]!='#' || map[ny2][nx2]!='#' || visit[ny1][nx1] || visit[ny2][nx2]) continue;

        visit[ny1][nx1] = visit[ny2][nx2] = 1;
        sol(ny2,nx2,nd,cnt+2,cmd+nxt);
        visit[ny1][nx1] = visit[ny2][nx2] = 0;
    }
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') cand.push_back({i,j});
        }
    }
    for(auto [y,x] : cand){
        sy=y, sx=x;
        for(int k=0;k<4;k++){
            sd=k;
            memset(visit,0,sizeof(visit));
            visit[y][x]=1;
            sol(y,x,k,1,"");
        }
    }
    char cd = 'v';
    if(ansd==1) cd= '>';
    else if(ansd==2) cd='^';
    else if(ansd==3) cd='<';

    printf("%d %d\n",ansy,ansx);
    printf("%c\n",cd);
    printf("%s",ret.c_str());
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/로봇이_지나간_경로.cpp

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

[난이도] level3
[유형] BFS

[풀이]
visit[100][100][4][4] 짜리 4차원 배열로 방문 체크를 해줘야하는 BFS 문제입니다.
visit[y][x][t][d] t : 현재시간, d : 현재방향
위와 같이 방향 뿐만 아니라 현재 시간에 따라서도 다른 상태가 될 수 있는 것을 주의해야 합니다.
T1%4 == T2%4 라면  T1과 T2는 같은 시간으로 쳐도 되므로 4의 공간만 필요합니다.

33번 라인의 코드
if(signals[seq[y][x][t%4]][0]!=d) continue; 는
t시간에 d의 방향으로 y,x에 방문한 상태일 때, y,x의 현재 신호가 유효한지를 체크해서 유효지 않으면 무시하는 로직입니다.

예를 들어, 차량의 방향이 위를 보고 있다면, 위 방향을 가리키고 있는 2,6,10 신호만 유효한 신호입니다.
signals vector에 신호 방향을 저장할 때, 0번 index에는 항상 좌,우회전이 아닌 직진 방향을 저장함으로써 0번 index만을 체크해서 유효성을 확인하였습니다.

#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int dy[4] = {0,-1,0,1}, dx[4] = {1,0,-1,0};
struct P{int y,x,d;};
vector<int> signals[13] = { {},
    {0,1,3},{1,0,2},{2,1,3},{3,0,2},
    {0,1},{1,2},{2,3},{3,0},
    {0,3},{1,0},{2,1},{3,2}
};
int N,T,seq[100][100][4];
bool visit[100][100][4][4];
set<pair<int,int>> ans;
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<4;k++)
                scanf("%d",&seq[i][j][k]);
    queue<P> q;
    q.push({0,0,1});
    visit[0][0][0][1]=1;
    ans.insert({0,0});
    int t=0;
    while(!q.empty()){
        int sz =q.size();
        if(t==T) break;
        while(sz--){
            auto [y,x,d] = q.front(); q.pop();
            if(signals[seq[y][x][t%4]][0]!=d) continue;

            for(auto k : signals[seq[y][x][t%4]]){
                int ny = y+dy[k], nx = x+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N||visit[ny][nx][t%4][k]) continue;
                visit[ny][nx][t%4][k]=1;
                q.push({ny,nx,k});
                ans.insert({ny,nx});
            }
        }
        t++;
    }
    printf("%d",ans.size());
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/차세대_지능형_교통시스템.cpp

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