프로그래밍

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

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

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

[풀이]
0~99 번째 구간의 제한속도와 실제 운행한 속도를 vector에 저장한 뒤 그 차의 최댓값을 구해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,u,v,ans;
int main(){
    scanf("%d%d",&N,&M);
    vector<int> a,b;
    while(N--){
        scanf("%d%d",&u,&v);
        while(u--) a.push_back(v);
    }
    while(M--){
        scanf("%d%d",&u,&v);
        while(u--) b.push_back(v);        
    }
    for(int i=0;i<100;i++) ans=max(ans,b[i]-a[i]);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/GBC.cpp