프로그래밍

https://codeforces.com/contest/1598/problem/A

[난이도] Div.2
[유형] BFS

[풀이]
BFS를 이용해 (2,n) 까지 도달이 가능하면 YES를 출력해줍니다.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
int t,n,mp[3][101];
bool visit[3][101];
int dy[4] = {1,0,1,-1};
int dx[4] = {1,1,0,1};
bool bfs(){

    queue<pair<int,int>> q;
    memset(visit,0,sizeof(visit));

    q.push({1,1});
    visit[1][1]=1;

    while(!q.empty()){

        auto [y,x] = q.front(); q.pop();
        if(y==2&&x==n) return true;
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(ny<1||nx<1||ny>2||nx>n||visit[ny][nx]||mp[ny][nx]) continue;
            visit[ny][nx]=1;
            q.push({ny,nx}); 
        }
    }
    return false;
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=2;i++)
            for(int j=1;j<=n;j++) scanf("%1d",&mp[i][j]);
        puts(bfs()?"YES":"NO");

    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/RoundEDU115-Div.2/A.cpp

https://www.acmicpc.net/problem/2513

[난이도] Gold3
[유형] Greedy

[풀이]
학교를 기준으로 먼 쪽에 있는 아파트부터 방문하면서 학생을 태워오는 Greedy 방식을 이용하면
통학버스의 이동거리를 최소로 할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N,K,S,ans;
vector<pair<int,int>> apart[2];
int main(){
    scanf("%d%d%d",&N,&K,&S);
    for(int i=0;i<N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(S>u) apart[0].push_back({u,v});
        else apart[1].push_back({u,v});
    }
    sort(apart[0].begin(),apart[0].end());
    sort(apart[1].begin(),apart[1].end());
    reverse(apart[1].begin(),apart[1].end());
    for(int k=0;k<2;k++){
        for(int i=0;i<apart[k].size();i++){
            int cur=0;
            for(int j=i;j<apart[k].size();j++){
                int t = cur + apart[k][j].second;
                if(t>=K){
                    apart[k][j].second = t - K;
                    cur=0;
                    ans+=2*abs(S-apart[k][i].first);
                    i=j;
                    if(t>K) i--;
                    break;
                }else{
                    cur+=apart[k][j].second;
                }
                if(j==apart[k].size()-1 && cur!=0){
                    ans+=2*abs(S-apart[k][i].first);
                    i=j;
                } 
            }
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2513.cpp

https://www.acmicpc.net/problem/19535

[난이도] Gold3
[유형] 트리

[풀이]
각 노드가 몇개의 인접한 노드를 가지고 있는지와 N-1개의 간선 (u,v) 만
저장해주면 문제를 풀 수 있습니다.
acnt[300001] 배열을 선언하여 acnt[i] : i번 노드와 연결된 노드 개수로 정의한 뒤 값을 저장해주었습니다.

D-트리의 개수 : 모든 간선 N-1개의 (u,v) 에 대해 (acnt[u]-1) * (acnt[v]-1) 의 값을 더해주면 됩니다.
                u와 연결된 u`, v와 연결된 v`을 이용해 [u` - u - v - v`] 형태의 D 트리를 만들 수 있습니다.
                1을 빼주는 이유는 [u-v] 간선을 빼주는 것입니다.

G-트리의 개수 : 1~N번 노드 i에 대해 조합 acnt[i]C3 을 구해주면 됩니다.
                acnt[i] 중 3개를 뽑으면 i 중심으로 3개의 간선이 연결된 트리가 되기 때문입니다.

#include <cstdio>
#include <vector>
using namespace std;
int N;
int acnt[300001];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        acnt[u]++, acnt[v]++;
        p.push_back({u,v});
    }
    long long a=0,b=0;
    for(auto [u,v] : p) a+=(acnt[u]-1)*(acnt[v]-1);
    for(int i=1;i<=N;i++) if(acnt[i]>=3) b+=(acnt[i]*(acnt[i]-1)*(acnt[i]-2))/6;
    b*=3;
    if(a>b) puts("D");
    else if(a<b) puts("G");
    else puts("DUDUDUNGA");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/19535.cpp

https://www.acmicpc.net/problem/16724

[난이도] Gold2
[유형] DFS

[풀이]
지도 밖으로 나가는 입력이 주어지지 않으므로
사이클을 찾아서 총 사이클의 개수를 세주면 됩니다.
dfs를 이용해서 현재 방문중이면 visit[y][x]=1로 체크하고
만약 다음 노드가 1로 체크되어 있다면 사이클을 찾은 것이므로 정답에 1을 더해줍니다.
또한 방문을 마칠때는 visit[y][x]=2로 체크해주어야 합니다.
왜냐하면 이미 발견되어 카운팅된 사이클로 접근하는 경우에는 이미 그 사이클에 쉼터가
존재하므로 카운팅을 해줄 필요가 없기 때문입니다. 이를 구분하기 위해 이미 쉼터에 갈 수 있는
노드들은 2로 체크해주었습니다.

#include <cstdio>
int N,M,ans;
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1},map[1000][1000];
int visit[1000][1000];
void dfs(int y,int x){
    visit[y][x]=1;
    int ny=y+dy[map[y][x]],nx=x+dx[map[y][x]];

    if(visit[ny][nx]==1) ans++;
    if(visit[ny][nx]==0) dfs(ny,nx);
    visit[y][x]=2;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char c;
            scanf(" %c",&c);
            if(c=='U') map[i][j]=1;
            else if(c=='R') map[i][j]=2;
            else if(c=='L') map[i][j]=3;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(visit[i][j]==0) dfs(i,j);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/16724.cpp

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

[난이도] level3
[유형] DFS

[풀이]
가장자리에는 얼음이 없다는 것이 보장되기 때문에
0,0에서부터 0(얼음) 인 점을 탐색하면서 4방향을 검사해서 얼음이 있으면 얼음의 좌표에 외부 공기에 접한 횟수를 카운팅 해줍니다.
그 뒤 2이상 카운팅된 얼음을 지워주는 것을 모든 얼음이 사라질때까지 반복하면 됩니다.

#include <cstdio>
#include <cstring>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int map[100][100],cnt[100][100],visit[100][100],ans;
void dfs(int y,int x){
    visit[y][x]=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>=M||visit[ny][nx]) continue;
        if(map[ny][nx]){
            cnt[ny][nx]++;
        }else{
            dfs(ny,nx);
        }
    }
}
bool exist(){
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(map[i][j]) return true;
    return false;
}
int main(){
    bool ok=0;
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf("%d",&map[i][j]);
            if(map[i][j]) ok=1;
        }
    while(ok){
        ans++;
        dfs(0,0);
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++) if(cnt[i][j]>=2) map[i][j]=0;
        ok=exist();
        memset(visit,0,sizeof(visit));
        memset(cnt,0,sizeof(cnt));
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/동계_테스트_시점_예측.cpp

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=405&submissionSn=SW_PRBL_SBMS_19088#hold

[난이도] level5
[유형] DP

[풀이]
K의 제한이 10^4로 증가하였기 때문에 복잡한 조립라인1 문제처럼 O(N*K^2) 풀이로는 시간내에 해결이 불가능 합니다.
대신 모든 j 작업장에서 다른 라인의 j+1 로 작업장으로 넘어가는데 걸리는 시간이 동일하기 때문에

Bottom-up 방식으로 dp[i][j] (1<=i<=K) 를 계산하기 전에
dp[i][j-1] (1<=i<=K) 중 최솟값 v를 미리 구해주면 아래와 같은 점화식을 세울 수 있습니다.

dp[i][j] = min(v+time[i][j]+mvtime[j-1],dp[i][j-1]+time[i][j]);

case 1) v+time[i][j]+mvtime[j-1] 은 j-1에서 j 작업으로 이동할 때 라인을 바꾼 경우입니다.
이 경우에는 이동간인 mvtime[j-1]을 더해준 것을 알 수 있습니다.

case 2) dp[i][j-1]+time[i][j] 은 라인을 바꾸지 않고 i라인에서 그대로 작업한 경우 입니다. mvtime[j-1]을 더해주지 않았습니다.

case 1에 라인을 바꾸지 않은 케이스 dp[i][j-1]+time[i][j]+mvtime[j-1] 가 포함되어 있습니다. 이때는
mvtime[j-1]을 더하지 않아야 하는데 더해서 문제가 발생할 것 같지만 이 값은 어차피
case 2인 dp[i][j-1]+time[i][j] 값보다 작아 무시되게 되어 문제가 되지 않습니다.

위와 같은 방법으로 O(N*K) 시간에 해결이 가능합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int K,N,time[10001][101],mvtime[101],dp[10001][101],inf=2e9;
int main(){
    scanf("%d%d",&K,&N);
    for(int j=1;j<=N;j++){
        for(int i=1;i<=K;i++) {
            scanf("%d",&time[i][j]);
            dp[i][j]=inf;
        }
        if(j==N) break;
        scanf("%d",&mvtime[j]);
    }
    for(int j=1;j<=N;j++){
        int v=inf;
        for(int i=1;i<=K;i++) v=min(v,dp[i][j-1]);
        for(int i=1;i<=K;i++) dp[i][j] = min(v+mvtime[j-1]+time[i][j],dp[i][j-1]+time[i][j]);
    }
    int ans=inf;
    for(int i=1;i<=K;i++) ans=min(dp[i][N],ans);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level5/복잡한_조립라인2.cpp

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

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 해결할 수 있습니다.
time[k][n] : k번 라인의 n번 작업장의 작업시간
mvtime[k][n][i] (i!=k) : k번 라인의 n번 작업장에서 i번 라인의 n+1번 라인으로 옮길때의 시간
dp[k][n] : k번 라인의 n번 작업부터 시작했을 때 N번 작업을 끝날때까지 걸리는 최소 시간

Top-Down DP를 이용하였으므로
sol(k,n) 은 dp[k][n]을 저장하며 리턴합니다.

점화식은 아래와 같습니다.
for(int i=1;i<=K;i++) dp[k][n]=min(dp[k][n],sol(i,n+1)+time[k][n]+mvtime[k][n][i]);
현재 작업 라인 k에서 1~K번 라인으로 넘어갈 수 있으며 그때의 이동시간인 mvtime을 더해주는 것을 알 수 있습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int K,N,time[101][101],mvtime[101][101][101],dp[101][101],inf=2e9;
int sol(int k,int n){
    if(n==N) return time[k][n];
    int& ret = dp[k][n];
    if(ret!=-1) return ret;
    ret=inf;
    for(int i=1;i<=K;i++) ret=min(ret,sol(i,n+1)+time[k][n]+mvtime[k][n][i]);
    return ret;
}
int main(){
    scanf("%d%d",&K,&N);
    for(int j=1;j<=N;j++){
        for(int i=1;i<=K;i++) scanf("%d",&time[i][j]);
        if(j==N) break;
        for(int i=1;i<=K;i++)
            for(int k=1;k<=K;k++)
                if(i!=k) scanf("%d",&mvtime[i][j][k]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level4/복잡한_조립라인1.cpp

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

[난이도] level3
[유형] 분할정복

[풀이]
N 제한이 굉장히 크기 때문에 일일이 계산해주면 안되고 재귀함수를 이용한 분할정복을 해주어야 합니다.

#include <cstdio>
using ll = long long;
ll K,P,N,mod=1000000007;
ll sol(ll n){
    if(n==1) return P;
    ll ret = sol(n/2);
    ret=(ret*ret)%mod;
    if(n%2) ret=(ret*P)%mod;
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&K,&P,&N);
    printf("%lld",(sol(N*10)*K)%mod);
}

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