프로그래밍

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

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

[난이도] level4
[유형] DP

[풀이]
이전 포스팅의 징검다리 문제보다 어려운 문제입니다.
이유는 아래와 같습니다.
1. N 제한이 10만을 넘어가므로 LIS를 구할 때 lower_bound를 이용하는 O(NlogN) 방법을 이용해야 합니다.
2. 단순 LIS를 구하는 것이 아닌 증가했다가(LIS) 감소하는(LDS) 변곡점이 있는 LIS + LDS sequence를 구해야 합니다.

0~N-1 번 돌을 변곡점으로 확정짓고 그 점부터 좌우로 퍼져나가는 LIS 혹은 LDS를 구하려고 하면 O(N^2logN)이 되어 시간초과에 빠지게 됩니다.

그러므로 앞에서부터 LIS를 한번 구해서 정보들을 저장 한 뒤, 뒤에서부터 LIS를 구해주면서
앞에서부터 LIS를 구해주면서 저장한 정보를 이용해 답을 구하는 O(NlogN) 해법을 이용해야 합니다.

아래 코드에서는 asc[300000], ascmax[300000] 배열을 선언하여 사용하였습니다.
asc[i] : 0~i 돌을 사용한 LIS의 크기.
ascmax[i] : 0~i 돌을 사용한 LIS의 마지막 값.

앞에서부터 LIS를 구하면서 위의 정보를 저장 한 뒤,

뒤에서부터 LIS를 돌려줍니다.
만약 i번 돌이 변곡점이 된다면 포함될 수 있는 최대 돌의 개수는
int v = dp.size() (N-1~i 돌을 사용한 LIS의 크기) + asc[i] (0~i 돌을 사용한 LIS의 크기)
이 됩니다.

하지만 여기서 예외처리 해주어야 할 것이 i번 돌이 좌측 LIS, 우측 LIS에 모두 포함될 경우입니다.
이 경우에는 변곡점 i번 돌을 1개 빼주어야 하므로
ascmax[i]를 확인해서 a[i]와 같은지, dp.back() (현재 LIS의 가장 큰 값) 이 a[i]와 같은지를 모두 체크해서
둘다 같다면 v-- 연산을 해주면 됩니다.

이는 모든 돌의 높이가 다르다는 것이 문제의 조건에 나와있기 때문에 가능합니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int ans,N,a[300001],asc[300001],ascmax[300001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);

    vector<int> dp = {a[0]};

    for(int i=1;i<N;i++){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        asc[i]=dp.size();
        ascmax[i]=dp.back();
    }

    dp.clear();
    dp.push_back(a[N-1]);

    for(int i=N-2;i>=0;i--){
        int idx = lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        if(idx == dp.size()) dp.push_back(a[i]);
        else dp[idx]=a[i];
        int v = dp.size()+asc[i];
        if(ascmax[i]==a[i] && dp.back()==a[i]) v--;
        ans=max(ans,v);        
    }
    printf("%d",ans==0?1:ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리2.cpp

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

[난이도] level3
[유형] DP

[풀이]
LIS(Longest Increasing Subsequence) 다이나믹 프로그래밍 문제입니다.
돌계단의 높이가 높아지는 순서로 선택하고, 그 개수를 최대로 해야하기 때문입니다.
N 제한 3000이기 때문에 O(N^2) 시간복잡도 풀이로 해결이 가능합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,a[3001],dp[3001];
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=n+1;i<=N;i++)
        if(a[n]<a[i]) ret=max(ret,1+sol(i));
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/징검다리.cpp

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

[난이도] level3
[유형] Greedy

[풀이]
강의 종료 시간을 기준으로 정렬하고 0번 강의는 무조건 선택한 뒤,
그 다음 추가가 가능한 강의를 index가 낮은 순서부터 탐색하면서 선택해주면 가장 많은 수의 강의를 추가할 수 있습니다.
현재 선택한 강의의 종료시간보다 다음 강의의 시작시간이 더 늦거나 같으면 선택할 수 있는 강의입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
pair<int,int> a[1000000];
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].second,&a[i].first);
    sort(a,a+N);
    for(int i=0;i<N;i++){
        int end = a[i].first;
        ans++;
        bool ok=0;
        for(int j=i+1;j<N;j++){
            if(end<=a[j].second){
                i=j-1;
                ok=1;
                break;
            }
        }
        if(!ok) break;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/강의실_배정.cpp

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

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

[풀이]
매 초마다 이전 초까지 쌓인 바이러스의 수에 P를 곱해 준 뒤, 이번 초에 추가되는 바이러스의 수를 더해주면서
N초까지 바이러스 수를 누적해가면 됩니다.

#include <cstdio>
using ll = long long;
int N;
ll P;
int main(){
    scanf("%lld%d",&P,&N);
    ll ret=0;
    for(int i=0;i<N;i++){
        ll v;
        scanf("%lld",&v);
        ret=(ret*P+v)%1000000007;
    }
    printf("%lld",ret);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/H-클린알파.cpp