프로그래밍

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);
}

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

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

[풀이]
각 카드가 몇번에 섞기 만에 원래 자리로 돌아올 수 있는지를 구하고,
0번인 카드를 제외한 이들의 최소공배수를 구하면 이것이 수열의 궤적이다.
각 카드마다 섞기 횟수를 구하면 시간초과가 나기 때문에
만약 1->3->5->1 이라면 1,3,5 전부 3번만에 원래 자리로 돌아오기 때문에 1을 구하면서
3,5도 같이 3으로 기록해줘야 한다.

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

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
int N,v[20001],cycle[20001];
ll gcd(ll a,ll b){
    ll c;
    if(a<b) swap(a,b);
    while(b!=0){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&v[i]);
    for(int i=1;i<=N;i++){
        if(cycle[i]!=0) continue;
        int k=i,cnt=1;
        vector<int> l;
        l.push_back(k);
        if(v[k]==i) cnt=0;
        while(v[k]!=i){
            k=v[k];
            l.push_back(k);
            cnt++;
        }
        for(int w : l) cycle[w]=cnt;
    }
    sort(v+1,v+1+N);
    ll ans=1;
    for(int i=1;i<=N;i++) {
        if(cycle[i]!=0) ans = lcm(ans,cycle[i]); 
    }
    printf("%lld",ans);
}

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

[난이도] Gold3
[유형] MST

[풀이]
u,v의 성별이 같은 edge는 버리고 크루스칼 알고리즘을 이용해 MST를 구해주면 된다.

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,uf[1001];
bool check[1001];
struct P{
    int u,v,d;
};
vector<P> vec;
int find(int a){
    if(a==uf[a]) return a;
    return uf[a]=find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a]=b;
    return 1;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) {
        char a;
        scanf(" %c",&a);
        check[i]=a=='M';
    }
    while(M--){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        if(check[u]!=check[v]) vec.push_back({u,v,d});
    }
    sort(vec.begin(),vec.end(),[](P& a,P& b)->bool{
        return a.d<b.d;
    });
    for(int i=1;i<=N;i++) uf[i]=i;

    int ans=0,cnt=0;
    for(int i=0;i<vec.size();i++){
        if(merge(vec[i].u,vec[i].v)){
            ans+=vec[i].d;
            if(++cnt==N-1){
                printf("%d",ans);
                return 0;
            }
        }
    }
    puts("-1");
}

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

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

[풀이]
아래 재귀함수를 이용하여 모든 케이스를 확인해준다.
sol(int c1,int c2,int r,int k0,int k1,int k2);
변수:
c1 : 경희가 내야할 손동작의 현재 index
c2 : 민호가 내야할 손동작의 현재 index
r : 이번 게임에 참가 못하는 사람의 index (0:지우, 1:경희, 2:민호)
k0 : 지우가 현재까지 이긴 횟수
k1 : 경희가 현재까지 이긴 횟수
k2 : 민호가 현재까지 이긴 횟수

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

#include <cstdio>
int N,K,map[10][10],seq[3][21];
bool use[10];
int sol(int c1,int c2,int r,int k0,int k1,int k2){
    if(k1==K||k2==K) return 0;
    if(k0==K) return 1;
    int a=-1,b;
    for(int i=0;i<3;i++){
        if(r!=i){
            if(a==-1) a=i;
            else b=i;
        }
    }
    int ka,kb,t;
    if(b==1) t=c1;
    else t=c2;
    kb=seq[b][t];
    if(a!=0){
        ka=seq[a][c1];
        if(map[ka][kb] < 2) {
            if(sol(c1+1,c2+1,a,k0,k1,k2+1)) return 1;
        }else{
            if(sol(c1+1,c2+1,b,k0,k1+1,k2)) return 1;
        }
    }else{
        for(int i=1;i<=N;i++){
            if(!use[i]){
                use[i]=1;
                int kk1=k1,kk2=k2,cc1=c1,cc2=c2;
                if(b==1) kk1++, cc1++;
                else kk2++, cc2++;
                                
                if(map[i][kb]<2){
                    if(sol(cc1,cc2,a,k0,kk1,kk2)) return 1;
                }else{
                    if(sol(cc1,cc2,b,k0+1,k1,k2)) return 1;
                }
                use[i]=0;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    for(int i=1;i<3;i++) 
        for(int j=0;j<20;j++) scanf("%d",&seq[i][j]);
    printf("%d",sol(0,0,2,0,0,0));
}

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

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

[풀이]
6번째 라인을 잘 살펴보면 i가 (1~N) 일때 모든 1+(N-1)/i의 합임을 알 수 있다.
그런데 N범위 10^9이므로 O(N)으로는 시간내에 풀수가 없다.

(N-1)/i 의 값이 똑같은 i들을 한번에 넘어가야한다.

이 과정은 아래 코드로 구현하였다.

    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }

각 변수의 의미는 다음과 같다.
i: (문제의 4번째 라인에서 i와 같은 의미)
cur: 현재 정답에 추가되어야 할 몫의 값 ((N-1)/i의 값)
d: cur과 다른 몫을 가지게 되는 i값이 i+d일때의 d값
(cur의 몫을 가지는 i는 총 d개이다. 그러므로 cur*d만큼을 ans에 더해준 것을 알 수 있다.)

d = ((N-1)%i)/((N-1)/i)+1 <= 이 로직으로 d를 구할 수 있는 이유는 다음과 같다.
현재 몫은 (N-1)/i이고, 나머지는 (N-1)%i이다.
i가 1씩 증가함에 따라 이 나머지는 (N-1)/i씩 줄어들게 된다.
그러므로 i에 ((N-1)%i)/((N-1)/i) 만큼을 더했을 때가 마지막으로 몫이 (N-1)/i인
순간이고, 여기서 i에 1을 더하게 되면 몫이 최초로 (N-1)/i보다 작아지게 된다. => (N-1)/i > (N-1)/(i+d)

글로 설명하기는 어렵기 때문에 각자가 잘 찾을 수 있는 규칙을 찾아보는 것을 추천한다.

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

#include <cstdio>
long long N,ans,d;
int main(){
    scanf("%lld",&N);
    for(long long i=1,cur=N-1;i<N;i+=d,cur=(N-1)/i){
        d = ((N-1)%i)/((N-1)/i)+1;
        ans+=cur*d;
    }
    printf("%lld",ans+N);
}

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

[난이도] Gold3
[유형] MST

[풀이]
피로도가 최소가 되게 할려면 edge cost가 1(내리막)인 edge를 우선으로 선택하게 해야하므로
오름차순으로 정렬, 최대가 되게 할려면 0(오르막)인 edge를 우선으로 선택하게 해야하므로
내림차순으로 정렬 뒤 Kruskal 알고리즘으로 MST를 구해주면 된다. 이 때, 총 가중치의 값은
필요 없고 선택된 edge중에 0(오르막)인 edge의 개수를 구해서 제곱해주면 최소,최대일때의
피로도를 각각 구할 수 있다.

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

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,uf[1001];
struct P{int a,b,c;};
vector<P> v;
int find(int a){
    if(uf[a]==a) return a;
    return uf[a]=find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a]=b;
    return 1;
}

int ksk(){
    for(int i=0;i<=N;i++) uf[i]=i;

    int cnt=0,ret=0;
    for(int i=0;i<v.size();i++){
        if(merge(v[i].a,v[i].b)){
            if(v[i].c==0) ret++;
            if(++cnt==N) break;
        }
    }
    return ret*ret;
}

int main(){
    scanf("%d%d",&N,&M);
    M++;
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c<v.c;
    });
    int ans = ksk();

    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c>v.c;
    });
    ans -= ksk();
    printf("%d",ans);
}

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

[난이도] Gold3
[유형] BFS

[풀이]
각 물건이 5개밖에 되지 않으므로 11111 이런식의 bitmask로 처리할 수 있다.
visit[50][50][1<<5] 크기의 배열을 선언해서 BFS를 해준다.
각 물건에 0~4 의 번호를 먹인 뒤 bit연산을 이용해 어떤 물건들을 챙긴 상태인지를
체크할 수 있다.

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

#include <cstdio>
#include <queue>
using namespace std;
int N,M,S,E,sy,sx,ey,ex,visit[50][50][1<<5];
char map[50][50];
int pos[50][50],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
struct P{
    int y,x,bmsk;
};
int main(){
    scanf("%d%d",&N,&M);
    int p=0;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='S') sy=i,sx=j;
            else if(map[i][j]=='E') ey=i,ex=j;
            else if(map[i][j]=='X') pos[i][j]=p++;
        }
    }
    queue<P> q;
    visit[sy][sx][0]=1;
    q.push({sy,sx,0});
    int cnt = 0;
    while(!q.empty()){
        int qsz = q.size();
        while(qsz--){

            P f = q.front(); q.pop();
            if(f.y==ey&&f.x==ex&&f.bmsk==(1<<p)-1){
                printf("%d",cnt);
                return 0;
            }
            for(int i=0;i<4;i++){
                int ny=f.y+dy[i], nx=f.x+dx[i];
                if(ny<0||nx<0||ny>=M||nx>=N||map[ny][nx]=='#') continue;

                if(map[ny][nx]=='X'){
                    int b = f.bmsk|(1<<pos[ny][nx]);
                    if(!visit[ny][nx][b]){
                        visit[ny][nx][b]=1;
                        q.push({ny,nx,b});
                    }
                }else{
                    if(!visit[ny][nx][f.bmsk]){
                        visit[ny][nx][f.bmsk]=1;
                        q.push({ny,nx,f.bmsk});
                    }
                }
            }
        }
        cnt++;
    }
}