프로그래밍

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

[난이도] Silver1
[유형] DFS

[풀이]
dfs 기본문제 입니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[501][501],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},cnt,ans;
int dfs(int y,int x){
    a[y][x]=2;
    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>=m||a[ny][nx]!=1) continue;
        ret+=dfs(ny,nx);
    }
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==1){
                cnt++;
                ans = max(ans,dfs(i,j));
            }
        }
    }
    printf("%d\n%d",cnt,ans);
}

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

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

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

[풀이]
지문에 적힌대로 구현하는 문제이므로 풀이법은 여러개 입니다.
저는 구조체에 인접한 칸에 좋아하는 학생의 수, 인접한 칸에 빈칸, (y,x) 좌표를 저장한 뒤
comparator 3개를 구현한 정렬을 이용해서 1,2,3 조건에 대한 처리를 해주었습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,board[21][21],ans;
set<int> fav[401];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
struct P{
    int f,e;
    pair<int,int> pos;
};
bool cmp1(P& u,P& v){
    return u.f > v.f; 
}
bool cmp2(P& u,P& v){
    return u.e > v.e; 
}
bool cmp3(P& u,P& v){
    return u.pos < v.pos; 
}
void sol(int n){
    vector<P> v;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(board[i][j]) continue;
            int f=0,e=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N) continue;
                if(board[ny][nx]==0) e++;
                else if(fav[n].find(board[ny][nx])!=fav[n].end())f++;
            }
            v.push_back({f,e,{i,j}});
        }
    }
    sort(v.begin(),v.end(),cmp1);
    vector<P> v2;
    for(auto p : v){
        if(v[0].f!=p.f) break;
        v2.push_back(p);
    }
    if(v2.size()==1) {
        board[v2[0].pos.first][v2[0].pos.second] = n;
        return;
    }
    sort(v2.begin(),v2.end(),cmp2);
    vector<P> v3;
    for(auto p : v2){
        if(v2[0].e!=p.e) break;
        v3.push_back(p);
    }    
    if(v3.size()==1) {
        board[v3[0].pos.first][v3[0].pos.second] = n;
        return;
    }
    sort(v3.begin(),v3.end(),cmp3);
    board[v3[0].pos.first][v3[0].pos.second] = n;
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N*N;i++){
        int n,v;
        scanf("%d",&n);
        for(int j=0;j<4;j++) {
            scanf("%d",&v);
            fav[n].insert(v);
        }
        sol(n);
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int cnt=0;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=N) continue;
                if(fav[board[i][j]].find(board[ny][nx])!=fav[board[i][j]].end()) cnt++;
            }
            if(cnt==1) ans+=1;
            if(cnt==2) ans+=10;
            if(cnt==3) ans+=100;
            if(cnt==4) ans+=1000;
        }        
    }
    printf("%d",ans);
}

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

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

[난이도] Gold3
[유형] MST

[풀이]
1번 컴퓨터가 아닌 다른 컴퓨터가 고장나거나, 다른 컴퓨터끼리의 연결이 끊어져도 어차피
1번 컴퓨터와 모든 컴퓨터가 연결되어 있기 때문에 안정적인 네트워크가 유지됩니다.
즉, 1번 컴퓨터가 고장난 경우만 고려하면 되므로,
1번 컴퓨터가 없을 때 나머지 컴퓨터들이 최소 스패닝 트리 (MST)를 이루도록 간선을 연결해주면 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,uf[1001],adj[1001][1001];
struct P{
    int u,v,d;
};
int find(int n){
    if(n==uf[n]) return n;
    return find(uf[n]);
}
bool merge(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v) return 0;
    uf[u] = v;
    return 1; 
}
bool cmp(P& a,P& b){
    return a.d < b.d;
}
bool check(){
    int r = find(2);
    for(int i=2;i<=N;i++){
        if(find(i)!=r) return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) uf[i]=i;
    while(M--){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[b][a]=adj[a][b]=1;
        merge(b,a);
    }
    vector<P> edges;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            int v;
            scanf("%d",&v);
            if(i==1||j==1||i>=j||adj[i][j]) {
                continue;
            }
            if(find(i)!=find(j)) {
                edges.push_back({i,j,v});
            }
        }
    }
    sort(edges.begin(),edges.end(),cmp);
    vector<pair<int,int>> ret;
    int sum=0;
    for(auto [u,v,d] : edges){
        if(merge(u,v)){
            ret.push_back({u,v});
            sum+=d;
            if(check()) break;
        }
    }
    printf("%d %d\n",sum,ret.size());
    for(auto [u,v] : ret){
        printf("%d %d\n",u,v);
    }
}

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

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

[난이도] Gold3
[유형] Greedy

[풀이]
pi가 항상 wi보다 크기 때문에 어떤 당근 i를 마지막 한번만 뽑아 먹는 것이 이득입니다.
중간에 뽑아서 다시 심게 되면 영양분이 p만큼 증가해야 되는 날에 다시 심게 되면서 w만 증가하게 되기 때문입니다.
결국 모든 당근을 한번씩만 뽑아먹어야 한다면, p가 클 수록 나중에 뽑아 먹는 것이 이득입니다.
p가 같다면 w가 큰 것을 선택해야 합니다.

정렬을 이용해 큰 (p,w) 부터 뽑으면서 계산한 뒤 정답에 더해주면 됩니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,T;
vector<pair<int,int>> v;
int main(){
    scanf("%d%d",&N,&T);
    for(int i=0;i<N;i++) {
        int w,p;
        scanf("%d%d",&w,&p);
        v.push_back({p,w});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());

    long long ans=0;
    for(int i=0;i<N;i++){
        auto [p,w] = v[i];
            ans+=w+(long long)p*(T-i-1);
    }
    printf("%lld",ans);
}

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

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

[난이도] Gold3
[유형] MST

[풀이]
최소스패닝트리 크루스칼 알고리즘을 이용하여 답을 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <vector>
using namespace std;
struct P{
    int u,v,d;
};
int N,uf[51],total;
vector<P> a;
bool cmp(P& l ,P& r){
    return l.d < r.d;
}
int find(int n){
    if(uf[n]==n) return n;
    return uf[n] = find(uf[n]);
}
bool merge(int u,int v){
    u = find(u);
    v = find(v);
    if(u==v) return 0;
    uf[u] = v;
    return 1; 
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int d=1;
            char c;
            scanf(" %c",&c);
            if(c=='0') continue;
            if(islower(c)) {
                d+=c-'a';
            }else{
                d+=26;
                d+=c-'A';
            }
            total+=d;
            if(i==j) continue;
            a.push_back({i,j,d});
        }
    }
    memset(uf,-1,sizeof(uf));
    for(int i=0;i<N;i++) uf[i]=i;
    sort(a.begin(),a.end(),cmp);
    int cnt=0,sum=0;
    for(int i=0;i<a.size();i++){
        auto [u,v,d] = a[i];
        if(merge(u,v)){
            sum+=d;
            if(++cnt==N-1) break;
        }
    }
    if(cnt<N-1) {
        puts("-1");
        return 0;
    }
    printf("%d",total-sum);
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
l,r,v (시작시간,종료시간,참여인원수)를 저장하는 구조체 P 배열을 선언한 뒤,
시작시간을 기준으로 정렬해줍니다.

그 뒤, lower_bound 사용을 위해 l에 대한 배열 s를 선언하여 따로 저장해줍니다.

DP[i] (sol(i))  : i~N-1 회의가 남았을 때, 회의를 진행할 수 있는 최대 인원

1) 회의 n를 선택 안한 경우
    sol(n+1) (n+1~N-1 회의가 남았을 때, 회의를 진행할 수 있는 최대 인원)

2) 회의 n를 선택한 경우,
    회의 n의 종료 시간보다 시작이 늦는 회의부터 선택할 수 있으므로
    lower_bound(s+n,s+N,a[n].r)-s; 와 같이 lower_bound를 이용하여
    회의 n의 종료시간보다 회의 시작이 늦는 가장 빠른 회의 i를 찾아 주면 됩니다.
    그러면 식은
    (회의 n에 참여하는 사람 수) + sol(i) 이 됩니다.

1,2의 max 값이 sol(i)의 값이 됩니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int l,r,v;
};
int N,dp[100001],s[100001];
P a[100001];
bool cmp(P& p,P& q){
    return p.l < q.l;
}
int sol(int n){
    if(n>=N) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    int i = lower_bound(s+n,s+N,a[n].r)-s;
    ret = max(sol(n+1),a[n].v+sol(i));
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
    sort(a,a+N,cmp);
    for(int i=0;i<N;i++) s[i] = a[i].l;
    printf("%d",sol(0));
}

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

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

[난이도] Silver2
[유형] DP

[풀이]
희이실 배정 2 문제와 다르게 N 제한이 100000으로 늘어났기 때문에 단순 브루트포스로는 풀 수 없습니다.
DP를 이용하면 쉽게 해결할 수 있습니다.
회의 K가 K-1,K+1 회의와 시간이 무조건 겹친다는 조건을 이용하면
회의 i를 선택한 경우와 선택하지 않은 경우를 나누는 점화식을 세울 수 있습니다.

DP[i] (sol(i)) : i~N-1번 회의중에 임의의 회의를 선택했을 때, 최대 인원의 수

1) i를 선택한 경우, i+1을 선택할 수 없으므로
   c[i]+sol(i+2)

2) i를 선택하지 않은 경우,
    sol(i+1)

sol(i) = max(c[i]+sol(i+2), sol(i+1))

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

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

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

[난이도] Silver2
[유형] 브루트포스

[풀이]
N 제한이 25밖에 안되기 때문에 2^N 개의 회의를 선택할 수 있는 경우의 수를 모두
구해보면 됩니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,a[26],b[26],c[26],ans,check[26];
void sol(int n){
    if(n==N) {
        int prev=-2,sum=0;
        bool ok=1;
        for(int i=0;i<N;i++){
            if(check[i]){
                if(i-prev==1) {
                    ok=0;
                    break;
                }else{
                    prev=i;
                    sum+=c[i];
                }
            }
        }
        if(ok) ans=max(ans,sum);
        return;
    }
    check[n]=1;
    sol(n+1);
    check[n]=0;
    sol(n+1);
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    sol(0);
    printf("%d",ans);
}

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