프로그래밍

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

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

[풀이]
골드바흐의 추측이라는 것을 알고 있어야 해결할 수 있는 문제입니다.

골드바흐의 추측은 2를 제외한 모든 짝수는 두개의 소수로 나타낼 수 있다는 것을 증명한 이론입니다.

즉 문제에서 A+B가 짝수이면서 2가 아니라면 무조건 YES를 출력하면 됩니다.

문제는 홀수인 경우인데, 홀수를 두개의 소수로 나누려면 한쪽은 무조건 짝수가 되어야 하는데

짝수인 소수는 2밖에 없으므로 소수 한개는 2로 확정됩니다.

그러므로 A+B-2 가 소수인지만 판별하면 되는데 이는 에라토스테네스의 체를 이용해

미리 2x10^6까지의 소수를 구해 놓음으로써 판별할 수 있습니다.

#include <cstdio>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int T;
ll A,B,np[2000001];
vector<ll> primes;
int main(){
    scanf("%d",&T);

    np[1]=1;
    for(int i=2;i<=2000000;i++){
        if(np[i]) continue;
        for(int j=i*2;j<=2000000;j+=i){
            np[j]=1;
        }
    }
    for(ll i=2;i<=2000000;i++) if(!np[i]) primes.push_back(i);

    while(T--){
        scanf("%lld%lld",&A,&B);
        ll sum = A+B;
        if(sum==2) {
            puts("NO");
            continue;
        }
        if(sum%2){
            sum-=2;
            bool ok=0;
            if(sum<=2000000) {
                puts(np[sum] ? "NO" : "YES");
                continue;
            }
            for(auto p : primes){
                if(sum<p) break;
                if(sum%p==0) {
                    ok=1;
                    break;
                }
            }
            puts(ok?"NO":"YES");
        }else{
            puts("YES");
        }
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
union-find의 find와 비슷한 개념을 이용하면 시간초과에 걸리지 않고 해결할 수 있습니다.
pair<int,int> dest[501][501] 를 선언하여 dest[y][x] 에는 y,x에서 출발 했을 때 최종으로
도착하는 점 {dest_y,dest_x}를 저장해 주었습니다.
board[y][x]의 수가 높은 수부터 탐색을 해주어야 하며
탐색 도중 다음 가야하는 점의 dest 값이 이미 구해져 있다면 이 값을 그대로 이용하며 탐색을 종료하면
시간 초과를 피할 수 있습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,pair<int,int>>> v;
int R,C,board[501][501],cnt[501][501];
int dy[8] = {-1,1,0,0,1,-1,1,-1};
int dx[8] = {0,0,1,-1,1,-1,-1,1};
pair<int,int> dest[501][501];
pair<int,int> sol(int y,int x){
    int minV=4e5,my,mx;
    for(int i=0;i<8;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<1||nx<1||ny>R||nx>C) continue;
        if(board[ny][nx] < minV){
            minV=board[ny][nx];
            my=ny;
            mx=nx;
        }
    }
    if(board[y][x] > minV){
        if(dest[my][mx].first!=0) return dest[y][x] = dest[my][mx];
        return dest[y][x] = sol(my,mx);
    }
    return dest[y][x]={y,x};
}
int main(){
    scanf("%d%d",&R,&C);
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++){
            scanf("%d",&board[i][j]);
            v.push_back({board[i][j],{i,j}});
        }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(auto p : v){
        auto [y,x] = p.second;
        if(dest[y][x].first==0) sol(y,x);
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            auto [y,x] = dest[i][j];
            cnt[y][x]++;
        }
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            printf("%d ",cnt[i][j]);
        }
        puts("");
    }   
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
N개의 물건이 1개 이상일 수 있는 배낭 문제입니다.
기본적인 배낭 문제의 풀이와 같으며,
다른 점은
{물건의 가치, 물건의 개수} pair로 N개를 저장한 뒤
i번 물건을 1,2,3,, (총 개수) 만큼 사용해볼 때의 모든 경우를 고려해주면 됩니다.
3중 for문이 나오기 때문에 시간초과에 걸릴 수 있어 답을 찾은 즉시 종료해주어야 합니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N,total,dp[50001];
pair<int,int> a[100];
int sol(){
    memset(dp,0,sizeof(dp));
    total=0;
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        total+=a[i].first * a[i].second;
    }
    if(total%2) return 0;
    dp[0]=1;
    for(int i=0;i<N;i++){
        for(int j=total/2;j>=0;j--){
            if(dp[j]) continue;
            int cur=0;
            for(int k=0;k<a[i].second;k++){
                cur+=a[i].first;
                if(j-cur>=0)  dp[j]=dp[j-cur];     
                if(dp[total/2]) return 1;
            }
        }
    }
    return dp[total/2];
}
int main(){
    int tc=3;
    while(tc--) {
        scanf("%d",&N);
        printf("%d\n",sol());
    }
}

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

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

[난이도] Gold1
[유형] 세그먼트 트리

[풀이]
세그먼트 트리를 이용하면 됩니다.

#include <cstdio>
using namespace std;
using ll = long long;
int N,Q,sidx;
ll segTree[3000000];

ll sum(int L,int R,int node,int cL,int cR){
    if(cR<L || R<cL) return 0;
    if(L<=cL && cR<=R) return segTree[node];
    int mid = (cL+cR)/2;
    return sum(L,R,2*node,cL,mid) + sum(L,R,2*node+1,mid+1,cR);
}

void update(int i,int v){
    i+=sidx;
    while(i>0){
        segTree[i]+=v;
        i/=2;
    }
}

int main(){
    scanf("%d%d",&N,&Q);
    for(sidx=1;sidx<N;sidx*=2);
    while(Q--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==1){
            update(b-1,c);
        }else{
            printf("%lld\n",sum(b-1,c-1,1,0,sidx-1));
        }
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
2차원 DP 문제 입니다.

DP[n][m] : 현재 지침 지수가 m이고 n분일 N-1분까지 달릴 수 있는 최대 거리

점화식은 n번 분에서 뛰거나 뛰지 않는 경우로 나누어서 생각할 수 있습니다.

Top-Down DP를 사용하였기 때문에 sol(n,m) 은 DP[n][m]을 구하고 return 합니다.

case 1) 뛰는 경우
    뛰면 m 값이 1증가 해야 하는데 만약 m+1>M이 된다면 문제의 조건에 의해 더이상 뛸 수 없으므로
    뛰어서는 안됩니다.
    m+1<=M 이라면 sol(n,m) = sol(n+1,m+1)+a[n] 이 됩니다.

case 2) 뛰지 않는 경우
    m>0 이라면 문제의 조건에 의해 m이 0이 될 때까지 쉬어야 하고
    적어도 마지막 분까지 쉬었을 때 m이 0이 되어야 하므로 n+m<=N 인 경우에만
    sol(n,m) = sol(n+m,0) 이 됩니다. (m은 다 쉬었기 때문에 0이 됨)

    만약 m==0 이라면 m값은 변화 없이 sol(n,m) = sol(n+1,0) 이 됩니다.

위의 값들 중 최댓값을 최종 sol(n,m)의 값으로 return 해야 합니다.

종료 조건 (n==N)
    n==N일 때 m은 0이어야 하므로 0이 아니라면 아주 큰 음수 inf를 return하여 최종 답에서 무시되도록 합니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,dp[10001][502],a[10001],inf=-9e8;
int sol(int n,int m){
    if(n==N) {
        if(m==0) return 0;
        return inf;
    }
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret=inf;
    if(m>0) {
        if(n+m<=N) ret=max(ret,sol(n+m,0));
    }else {
        ret=max(ret,sol(n+1,0));
    }

    if(m+1<=M) ret=max(ret,sol(n+1,m+1)+a[n]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

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

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

[난이도] Gold4
[유형] 누적합

[풀이]
누적합을 미리 구해준 뒤 나올 수 있는 모든 부분행렬을 구해보면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,board[201][201],ans=-9e8;
int sol(int h,int w){
    int ret=-9e8;
    for(int i=1;i<=N-h+1;i++)
        for(int j=1;j<=M-w+1;j++)
            ret=max(ret,board[i+h-1][j+w-1] - board[i-1][j+w-1] - board[i+h-1][j-1] + board[i-1][j-1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%d",&board[i][j]);
            board[i][j]+=board[i][j-1]+board[i-1][j]-board[i-1][j-1];
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            ans=max(ans,sol(i,j));
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] 슬라이딩 윈도우

[풀이]
w의 모든 순열을 구해서 풀기에는 최대 길이가 3000이므로 너무 많은 연산이 필요합니다.

s에 포함되어 있는 연속된 w의 순열을 찾기만 하면 된다는 것을 이용하면 O(M) (s의 길이 M) 에 해결이 가능합니다.

w의 길이가 N, s의 길이가 M일 때,
s에 포함된 w의 순열은 길이가 N이면서 w에 포함된 모든 알파벳을 하나도 빠짐없이 사용할 string을 찾으면 됩니다.

wcnt[100], scnt[100]을 선언하여 wcnt[100]에는 w의 각 문자가 몇개씩 들어있지를 저장해놓고,

현재 확인중인 문자열의 맨 앞 index를 의미하는 sidx를 0으로 설정해놓고.
s의 0번 문자부터 확인하면서 아래와 같이 처리해줍니다.

현재 확인 중인 i번째 문자가 c일 때,
c = s[i]
if scnt[c-'A'] < wcnt[c-'A']
    c는 최대 wcnt[c-'A']만큼 사용이 가능한데 아직 scnt[c-'A']에 여유가 있으므로
    문자열에 포함시켜 주고 snct[c-'A']++ 를 해줍니다.

else
    wcnt[c-'A']를 모두 사용하였으므로 현재 문자 c를 문자열에 포함시킬 수 없습니다.
    c가 나올 때까지 sidx를 뒤로 옮기며 scnt 배열을 수정해줍니다. c가 j번째 index에 나온다면
    sidx를 j+1로 수정해주면 i번 문자 c를 포함시킬 수 있게 됩니다.
    만약 c를 발견하지 못했다면 wcnt[c-'A']==0 이라는 의미이고 sidx i+1부터 하여 다시 탐색을 시작해야 합니다.

매 루프마다 i-sidx+1==N 를 만족한다면 길이가 N인 w의 수열을 찾은 것이므로 ans++을 해줍니다.

#include <iostream>
#include <string>
using namespace std;
string w,s;
int N,M,wcnt[100],scnt[100],ans;
int main(){
    cin >> N>>M>>w>>s;
    for(auto c : w) wcnt[c-'A']++;
    int sidx=0;
    for(int i=0;i<M;i++){
        char c = s[i];
        if(scnt[c-'A'] < wcnt[c-'A']){
            scnt[c-'A']++;
        }else{
            for(int j=sidx;j<=i;j++){
                if(s[i]==s[j]){
                    sidx=j+1;
                    break;
                }
                scnt[s[j]-'A']--;
            }
        }
        if(i-sidx+1==N) ans++;
    }
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] 에라토스테네스의 체

[풀이]
구해야하는 값 ret이 1~N 모든 수로 나누어 떨어지려면
ret을 소인수 분해 해서 a^k1 * b^k2 * c^k3... 꼴이 됐을 때,
a,b,c...인 어떤 소수 p는 1~N 숫자 중 p를 가장 많이 가지고 있는 숫자가 가지고 있는 만큼
가지고 있어야 ret을 1~N의 모든 수를 나누어 봤을 때, p가 부족해서 나누지 못하는 경우가 생기지 않습니다.

그러므로 전체 풀이는 아래와 같습니다.

1) 에라토스테네스의 체를 이용해 N보다 작은 모든 소수를 구해서 vector에 미리 저장,
2) 각 소수 p의 거듭제급 p^k 중 N보다 작으면 가장 큰 수를 구해서 ret에 곱해줌

연산 중 int 범위를 넘어갈 수 있으므로 long long을 적절히 사용해줍니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N;
int mod=987654321;
bool prime[1000001];
int main(){
    scanf("%d",&N);
    for(int i=2;i<=N;i++){
        for(int j=i*2;j<=N;j+=i){
            prime[j]=1;
        }
    }
    vector<int> primes;
    for(int i=2;i<=N;i++){
        if(!prime[i]) primes.push_back(i);
    }
    ll ret=1;
    for(auto p : primes){
        if(p>N) break;
        ll k = p; 
        while(k*p<=N) k*=p;
        ret=(ret*k)%mod;
    }
    printf("%lld",ret);
}

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