프로그래밍

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

[난이도] Gold3
[유형] DFS

[풀이]
tree 구조이므로 1부터 시작하는 dfs를 돌려주면서 각 노드의 양의 수만큼 더해주고, 늑대의 수만큼 빼주면
루트인 1에 몇마리의 양이 도착하는지 알 수 있습니다.
늑대+양이 음수가 될때는 0으로 초기화를 해주고, 자료형이 int 형을 넘어갈 수 있는점을 주의해야 합니다.

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
vector<int> adj[123457];
int N,cnt[123457];
ll dfs(int p,int n){
    ll sum=cnt[n];
    for(auto nxt : adj[n]){
        if(nxt!=p) sum+=dfs(n,nxt);
    }
    return sum < 0 ? 0 : sum;   
}
int main(){
    scanf("%d",&N);
    for(int i=2;i<=N;i++){
        char c;
        int a,p;
        scanf(" %c%d%d",&c,&a,&p);
        if(c=='W') a=-a; 
        adj[i].push_back(p);
        adj[p].push_back(i);
        cnt[i]=a;
    }
    printf("%lld",dfs(-1,1));
}

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

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

[난이도] Gold4
[유형] 투포인터

[풀이]
입력문자열의 앞부터 확인하면서 a[26] 배열에 각 문자를 몇개 사용했는지를 기록해줍니다.
그러다 N개의 문자를 넘게 사용하게 되면 현재 체크중인 문자열의 맨 앞 index부터 문자열에서
제거해주면서 a[26] 배열을 업데이트 해줍니다. a[k] > 0 이었다가 a[k] == 0 인 문자가 나타나면
이제 맨 뒤 쪽에 이어서 문자를 추가해줄 수 있기 때문에 뒤쪽에 다시 문자들을 붙혀줍니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,a[26],ans,v,start;
string s;
int main(){
    cin >> N >> s;
    string cur;
    for(int i=0;i<s.size();i++){
        int cnt=0;
        for(int j=0;j<26;j++) {
            if(a[j]>0) cnt++;
        }
        if(cnt<N || a[s[i]-'a']){
            v++;
            a[s[i]-'a']++;
            ans=max(ans,v);
            continue;
        }
        for(int j=start;j<=i;j++){
            v--;
            if(--a[s[j]-'a'] == 0){
                start=j+1;
                break;
            }
        }
        i--;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] BFS

[풀이]
최초 유포자들부터 queue에 넣고 bfs를 돌려주면 됩니다.
주의할 점이 루머를 믿는 사람에 인접한 사람을 검사할 때,
그 사람의 주변에 루머를 믿는 사람이 절반 이상이어도 바로 visit 체크를 하면 안되고
모든 검사가 끝난 뒤에 한번에 q에 넣고, visit 체크를 해주어야 합니다.
왜냐하면 다음 검사에 영향을 받을 수 있기 때문입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector<int> adj[200001];
int N,M,visit[200001],ip,ans[200001];
queue<int> q;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        while(1){
            scanf("%d",&ip);
            if(ip==0) break;
            adj[i].push_back(ip);
        }
    }
    memset(ans,-1,sizeof(ans));
    scanf("%d",&M);
    for(int i=0;i<M;i++) {
        scanf("%d",&ip);
        q.push(ip);
        visit[ip]=1;
        ans[ip]=0;
    }
    int time=1;
    while(!q.empty()){
        int sz = q.size();
        vector<int> tmp;
        while(sz--){
            auto qf = q.front(); q.pop();

            for(auto nxt : adj[qf]){
                if(!visit[nxt]){
                    int cnt=0;
                    for(auto nadj : adj[nxt]){
                        cnt+=visit[nadj];
                    }
                    if(adj[nxt].size() <= 2*cnt){
                        tmp.push_back(nxt);
                        ans[nxt]=time;
                    }
                }
            }
        }
        for(auto t : tmp){
            q.push(t);
            visit[t]=1;
        }
        time++;
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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

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

[난이도] Gold4
[유형] Greedy

[풀이]
순위가 낮은 (숫자 큰) 사람을 빠르게 경기를 시켜서 빠르게 탈락시킬수록
랭킹의 차이의 합을 최소로 만드는데 유리하므로
경기를 매칭 시킬 때, 현재 남은 사람중에 랭킹이 가장 낮은 선수를 무조건 포함시켜 주는 방식으로
풀면 최적의 경우가 됩니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
int main(){
    scanf("%d",&N);
    vector<int> v(N);
    for(int i=0;i<N;i++) scanf("%d",&v[i]);
    while(v.size()>1){
        int idx = max_element(v.begin(),v.end())-v.begin();
        int l=0,r=0;
        if(idx-1>=0) l=v[idx-1];
        if(idx+1<v.size()) r=v[idx+1];
        ans+=v[idx]-max(l,r);
        vector<int> tmp;
        for(auto c : v){
            if(c!=v[idx]) tmp.push_back(c);
        }
        v=tmp;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
아래와 같은 정의 4차원 dp를 이용하면 해결이 가능합니다.
이전 상태와, 현재 방향을 각각 f,d에 저장했습니다.
dp[y][x][f][d] : 현재 방향이 d (0:세로, 1:가로) 이고, 이전 이동 상태가 f (0:방향 변경x 1:방향 변경o) 이면서
                 현재 위치가 (y,x)일 때, (h,w)까지 도달하는 경우의 수.

#include <cstdio>
#include <cstring>
int w,h,dp[101][101][2][2];
int sol(int y,int x,int f,int d){
    if(y>h||x>w) return 0;
    if(y==h&&x==w) return 1;
    int& ret = dp[y][x][f][d];
    if(ret!=-1) return ret;
    if(d==0){
        ret=sol(y+1,x,0,0);
        if(!f) ret = (ret+sol(y,x+1,1,1))%100000;
    }else{
        ret=sol(y,x+1,0,1);
        if(!f) ret = (ret+sol(y+1,x,1,0))%100000;
    }
    return ret;
}
int main(){
    scanf("%d%d",&w,&h);
    memset(dp,-1,sizeof(dp));
    printf("%d",(sol(2,1,0,0)+sol(1,2,0,1))%100000);
}

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

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

[난이도] Bronze2
[유형] 수학

[풀이]
s가 1이 나올때마다 방향을 반대로 바꿔주고,
회전수는 1로 시작해서 b/a를 계속 곱해주면 됩니다. 정수인 답이 나온다는 조건이 있기 때문에
회전수는 계속 정수로 유지될 것이기 때문에 계속 나눠주어도 됩니다.

#include <cstdio>
int M,d,cur=1;
int main(){
    scanf("%d",&M);
    while(M--){
        int a,b,s;
        scanf("%d%d%d",&a,&b,&s);
        if(s==1) d=1-d;
        cur=cur*(double)b/a;
    }
    printf("%d %d",d,cur);
}

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

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

[난이도] Bronze3
[유형] 수학

[풀이]
각 학교에서 사솨개수%학생수 만큼 사과가 남습니다.

#include <cstdio>
int N,a,b,ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d%d",&a,&b);
        ans+=b%a;
    }
    printf("%d",ans);
}

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

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

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

[풀이]
300초, 60초, 10초짜리 버튼 순으로 많이 사용하는 것이 유리하므로
T를 300으로 나눈 몫이 300초 버튼을 가장 많이 사용할 수 있는 갯수이고,
T를 300으로 나눈 나머지가 300초 버튼을 사용하고 남은 시간입니다.
이를 다시 60초, 10초에 대해서 연산해주어서 각 버튼을 몇번 사용하는지 구하면 됩니다.
만약 T가 10으로 나누어지지 않는다면 주어진 버튼으로 구할 수 없으므로 -1을 출력해주면 됩니다.

#include <cstdio>

int T;
int main(){
    scanf("%d",&T);
    if(T%10) {
        puts("-1");
        return 0;
    }
    printf("%d ",T/300);
    T%=300;
    printf("%d ",T/60);
    T%=60;
    printf("%d ",T/10);
    T%=10;
}

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