프로그래밍

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

[난이도] Gold4
[유형] DP

[풀이]
map[100][100][2] 배열을 선언해서
(y,x) -> (y+1,x) 길이 막혀있는 경우 map[y][x][0]=1,
(y,x) -> (y,x+1) 길이 막혀있는 경우 map[y][x][1]=1 로 체크한 뒤
DP로 모든 경우를 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
int dy[2]={1,0},dx[2]={0,1};
int K,N,M,map[101][101][2];
ll dp[101][101];
ll sol(int y,int x){
    if(y==N&&x==M) return 1;
    ll& ret = dp[y][x];
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=0;i<2;i++){
        if(!map[y][x][i]){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<=N&&nx<=M) ret+=sol(ny,nx);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    while(K--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a>c)swap(a,c);
        else if(b>d)swap(b,d);
        if(a<c) map[a][b][0]=1;
        else if(b<d) map[a][b][1]=1;
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(0,0));
}

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

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

[난이도] Gold4
[유형] 정수론

[풀이]
골드바흐의 추측이라는 정수론 개념을 이용해서 풀어야 하는 문제이다.
https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

일단 시간내에 소수를 구하기 위해 에라토스테네스의 체를 이용해 소수를 미리 구해준다.

골드바흐의 추측 : '2보다 큰 모든 짝수는 두 소수의 합으로 표현가능하다'

4개 소수의 합으로 표현하기 위해서 N은 무조건 8보다는 커야 한다.
N이 홀수인 경우, N에서 2,3을 빼주어서 짝수를 만든 뒤 N-5를 두개의 소수로 만들 수 있는 짝을 찾는다.
N이 짝수인 경우, N에서 2,2를 빼준 뒤에 N-4를 두개의 소수로 만들 수 있는 짝을 찾는다.

#include <cstdio>
#include <vector>
using namespace std;
int N;
bool a[1000001];
int main(){
    scanf("%d",&N);
    a[0]=a[1]=1;
    for(int i=2;i<=N;i++){
        for(int j=2*i;j<=N;j+=i) a[j]=1;
    }
    vector<int> ans;
    if(N<8) puts("-1");
    else{
        if(N%2){
            ans.push_back(2);
            ans.push_back(3);
            for(int i=2;i<=N;i++){
                if(!a[i] && !a[N-5-i]){
                    ans.push_back(i);
                    ans.push_back(N-5-i);
                    break;
                }
            }
        }else{
            ans.push_back(2);
            ans.push_back(2);
            for(int i=2;i<=N;i++){
                if(!a[i] && !a[N-4-i]){
                    ans.push_back(i);
                    ans.push_back(N-4-i);
                    break;
                }
            }            
        }
    }
    for(auto p : ans) printf("%d ",p);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 이용해 칭찬 그래프를 만들고 칭찬을 받은 사람부터 dfs를 시작해
방문하는 모든 부하들에게 칭찬을 더해주면 된다.
이 때, 칭찬의 총 갯수 M마다 dfs를 돌면 시간초과가 나므로 사람 i에 대한 칭찬을 미리 모두 더한 뒤
dfs를 돌려야 한다.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N,M,ans[100001],s[100001];
vector<int> adj[100001];
void dfs(int n,int k){
    ans[n]+=k;
    for(auto nxt : adj[n]) dfs(nxt,k);
}

int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=1;i<=N;i++){
        int u;
        scanf("%d",&u);
        if(u!=-1) adj[u].push_back(i);
    }
    while(M--){
        int a,w;
        scanf("%d%d",&a,&w);
        s[a]+=w;
    }
    for(int i=2;i<=N;i++){
        if(s[i]>0) dfs(i,s[i]);
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
기본 LCS를 변경한 DP로 풀 수 있다.

DP[i][j] : 바꿔야할 문자열이 a, 목표 문자열이 b일때 a[1...i],b[1...j]까지의 a,b에 대한 최소 편집 개수
a[i]==b[j] 이면 DP[i][j] = DP[i-1][j-1] 이며
아닌 경우 DP[i-1][j-1] , DP[i-1][j] , DP[i][j-1] 중 최솟값에 1을 더한 값이 된다.
DP[i-1][j-1]인 경우는 a[i]를 b[j]로 바꾸는 연산, DP[i-1][j],DP[i][j-1]인 경우는 문자 하나를 추가하는 연산이다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
string a,b,c;
int dp[1001][1001];
int main(){
    cin >> a >> b;
    a='A'+a;
    b='B'+b;
    int n=a.size(), m=b.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0&&j==0) continue;
            if(i==0){
                dp[i][j]=j;
                continue;
            }
            if(j==0){
                dp[i][j]=i;
                continue;
            }
            if(a[i]==b[j]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
        }
    }
    cout << dp[n-1][m-1] << endl;;
}

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

https://codeforces.com/contest/1472/problem/D

[난이도] Div.3
[유형] Greedy

[풀이]
홀수, 짝수인 숫자를 따로 vector에 보관 후 정렬하고,
Alice 차례일때 현재 홀수중 최댓값이 짝수중 최댓값보다 크다면 홀수를 선택해서 Bob이 선택못하도록 하고,
짝수가 더크다면 짝수를 선택하는 방식으로 하는것이 Alice에게 최적이다.
Bob의 차례인 경우엔 그 반대로 하면 된다.

다른 풀이를 보고 알 수 있었는데
홀수,짝수 상관없이 정렬 후 큰 수부터 선택해도 Alice,Bob 모두 optimal 하므로 이 방식으로 풀어도 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int tc,N;
int main(){
    scanf("%d",&tc);
    
    while(tc--){
        scanf("%d",&N);
        vector<ll> odd,even;
        for(int i=0;i<N;i++){
            ll v;
            scanf("%lld",&v);
            if(v%2) odd.push_back(v);
            else even.push_back(v);
        }
        sort(odd.begin(),odd.end());
        sort(even.begin(),even.end());
        
        int curo=odd.size()-1,cure=even.size()-1;
        ll alice=0,bob=0;
        for(int i=0;;i++){
            if(curo<0&&cure<0) break;
            if(i%2==0){
                if(curo<0){
                    alice+=even[cure--];
                    continue;
                }
                if(cure<0){
                    curo--;
                    continue;
                }

                if(odd[curo] <= even[cure]){
                    alice+=even[cure--];
                }else{
                    curo--;
                }
            }else{
                if(curo<0){
                    cure--;
                    continue;
                }
                if(cure<0){
                    bob+=odd[curo--];
                    continue;
                }

                if(odd[curo] >= even[cure]){
                    bob+=odd[curo--];
                }else{
                    cure--;
                }
            }
        }
        if(alice>bob) puts("Alice");
        else if(alice<bob) puts("Bob");
        else puts("Tie");
        //printf("alice:%d, bob:%d\n",alice,bob);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/D.cpp

https://codeforces.com/contest/1472/problem/C

[난이도] Div.3
[유형] DP

[풀이]
DP(i) (1<=i<=N) : index i를 선택했을 얻을 수 있는 점수.
점화식 : DP(i) = A[i] + DP(i+A[i])

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

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/C.cpp

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

[난이도] Div.3
[유형] 수학

[풀이]
2^(W가 2로 나눠지는 횟수) * 2^(H가 2로 나눠지는 횟수) 가 최대 자를 수 있는 조각임을 알 수 있다.

#include <cstdio>
using ll = long long;
int tc,H,W;
ll N;
int main(){
    scanf("%d",&tc);
    while(tc--){ 
        scanf("%d%d%lld",&W,&H,&N);
        int wc=1,hc=1;
        while(W%2==0){
            wc*=2;
            W/=2;
        }
        while(H%2==0){
            hc*=2;
            H/=2;
        }
        if(wc*hc >= N) puts("YES");
        else puts("NO");
    }
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
DP[l][r] : index l부터 index r까지의 문자열을 팰린드롬으로 만들기 위해 삽입해야할 문자의 최수 갯수

점화식 : DP[l][r] = min(
DP[l+1][r]+1, s[l]과 같은 문자를 r+1에 삽입할 때
DP[l][r-1]+1, s[r]과 같은 문자를 l-1에 삽입할 때
DP[l+1][r-1]+1 (if s[l]==s[r]인 경우)
)

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

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N,dp[5001][5001],inf=9e8;
string s;
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = inf;
    if(s[l]==s[r]) ret = min(ret,sol(l+1,r-1));
    ret = min(ret,1+sol(l+1,r));
    ret = min(ret,1+sol(l,r-1));
    return ret;
}
int main(){
    cin >> N >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,N-1);
}