프로그래밍

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

[난이도] Gold3
[유형] DP

[풀이]
dp[i] : 1~i번 기지국까지 설치 했을 때의 최소 설치 비용.

dp[i]를 구하기 위해서는 i를 어느 박스에 포함시킬지를 정해야한다.
만약 어떤 j~i를 이은 박스에 포함시키려면 j~i 박스의 최솟값 + dp[j-1] (j-1번까지 설치했을 때의 최솟값)을 더해주면 된다.

점화식
dp[i]= min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); (j : 1~i, mH : 1~i까지 높이의 최댓값, a.first : x좌표)

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N,dp[10001],inf=9e8;
pair<int,int> a[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    sort(a+1,a+N+1);
    for(int i=1;i<=N;i++){
        int mH=0;
        dp[i]=inf;  
        for(int j=i;j>=1;j--){
            mH=max(mH,abs(a[j].second));
            dp[i]=min(dp[i],dp[j-1]+max(2*mH,a[i].first-a[j].first)); 
        }
    }
    printf("%d",dp[N]);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : 자리수가 n이면서 m으로 시작하는 수의 개수

#include <cstdio>
int t,N;
long long a[65][10];
int main(){
    scanf("%d",&t);
    for(int i=0;i<10;i++) a[1][i]=1;
    for(int i=2;i<65;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<=j;k++) 
                a[i][j]+=a[i-1][k];
    while(t--){
        scanf("%d",&N);
        long long ans=0;
        for(int i=0;i<10;i++) ans+=a[N][i];
        printf("%lld\n",ans);
    }
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
dp[i][k] (i:0~N-1, k:0,1)
dp[i][0] : 숫자 한개를 제거하지 않은 i번째로 끝나는 수열의 합 중 최댓값
dp[i][1] : 숫자 한개를 제거한 i번째로 끝나는 수열의 합 중 최댓값

k=0을 구하는 법 : dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i]
숫자를 제거하지 않을 것이므로 dp[i-1]에 a[i]를 이어붙이면 된다. 단, dp[i-1]이 음수인 경우에는
dp[i-1]을 합치는 것은 합을 줄어들게 하므로 a[i]만 dp[i][0]으로 설정한다.

k=1을 구하는 법 : dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]);
dp[i-1][0]은 a[i] (제일 오른쪽)을 제거하는 경우인데, 아직 숫자가 제거되지 않았어야 하므로 dp[i-1][0]이다.
dp[i-1][1]+a[i]는 이미 숫자가 제거된 dp[i-1][1]에 a[i]를 이어붙이는 케이스이다.

위의 방법으로 O(N)에 해결이 가능하다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,a[100000],dp[100000][2],ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    dp[0][0]=a[0];
    ans=a[0];
    for(int i=1;i<N;i++){
        dp[i][0] = dp[i-1][0]<0 ? a[i] : dp[i-1][0]+a[i];
        dp[i][1] = max(dp[i-1][0],dp[i-1][1]+a[i]); 
        ans=max(dp[i][0],ans);
        ans=max(dp[i][1],ans);
    }
    printf("%d",ans);
}

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

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

[난이도] Gold5
[유형] DP

[풀이]
DP[y][x][k] : 파이프의 끝 부분이 y,x에 있고, k번 방향으로 위치해 있을 때 (0: 가로, 1:세로, 2:대각선)
N-1,N-1까지 갈 수 있는 경우의 수.

#include <cstdio>
#include <cstring>
using namespace std;
int N,a[16][16],dp[16][16][3];
bool check(int y,int x){
    return y>=0&&x>=0&&y<N&&x<N&&!a[y][x];
}
bool all(int y,int x){
    return check(y,x+1) && check(y+1,x) && check(y+1,x+1);
}
int sol(int y,int x,int k){
    if(y==N-1&&x==N-1) return 1;
    int& ret = dp[y][x][k];
    if(ret!=-1) return ret;
    ret = 0;
    if(k==0){
        if(check(y,x+1)) ret+=sol(y,x+1,0);
    }else if(k==1){
        if(check(y+1,x)) ret+=sol(y+1,x,1);
    }else{
        if(check(y,x+1)) ret+=sol(y,x+1,0);
        if(check(y+1,x)) ret+=sol(y+1,x,1);
    }
    if(all(y,x)) ret+=sol(y+1,x+1,2);
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) scanf("%d",&a[i][j]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,1,0));
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
1,2,3,4,...N 순서로 동그랗게 앉아 있다고 가정했을 때,
1이 누구와 악수하는지를 고정해놓는 방식으로 풀면 DP로 답을 구할 수 있다.
예를 들어
1,4가 악수하는 경우의 수 : (2,3)이 악수하는경우의 수 * (5,6,...,N)이 악수하는 경우의 수
1,6가 악수하는 경우의 수 : (2,5)이 악수하는경우의 수 * (7,...,N)이 악수하는 경우의 수
...
...
위의 경우를 모두 더한 것이 답이다.

이것을 점화식으로 나타내면 아래와 같다.
DP[n] = DP[i] * DP[n-2-i] (0<=i<=n-2)

info) 카탈란 수라는 수학적 개념이라고 한다.

#include <cstdio>
#include <cstring>
using ll = long long ;
int N,mod=987654321;
ll dp[10001];
ll sol(int n){
    if(n==0||n==2) return 1;
   
    ll& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=0;i<=n-2;i+=2){
        ret+=sol(i)*sol(n-2-i);
        ret%=mod;
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(N));
}

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

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

[난이도] Gold2
[유형] DP

[풀이]
높이순으로 정렬해놓고 어떤 그림들을 빼야 효율적인지를 정해야 한다.
일일히 구해보면 시간초과가 나므로 메모제이션을 이용해야 한다.
DP[i] : i~N-1번째 그림들에서 얻을 수 있는 최댓 값.

i번 그림은 포함될수도 있고, 제거(제일 뒤로 보내기)할 수도 있다.
1) 포함되는 경우.
만약 i번 그림이 포함된다면 p=(i번 그림의 높이 + S)보다 낮은 그림들은 가려져서 포함될 수 없다.
그러므로 p보다 높이가 높은 가장 작은 index를 k라고 했을 때,
(i번 그림의 가격 + DP[k])이 첫번째 케이스의 결과이다.

2) 포함되지 않는 경우.
i번 그림이 아무것도 가리지 않게 되므로 DP[i]==DP[i+1]이므로
DP[i+1]이 두번째 케이스의 결과이다.

=> DP[i] = 1,2케이스 중에 더 큰 값.

Top-Down 방식으로 구현하였다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,S,dp[300000],h[300000];
pair<int,int> a[300000];
int sol(int n){
    if(n>=N) return 0;
    int& ret=dp[n];
    if(ret!=-1) return ret;

    int p = a[n].first+S;
    int k = lower_bound(h,h+N,p)-h;
    ret=sol(n+1);
    ret=max(ret,a[n].second+sol(k));

    return ret;
}
int main(){
    scanf("%d%d",&N,&S);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        h[i]=a[i].first;
    }
    sort(h,h+N);
    sort(a,a+N);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
DP[y][x] : y,x에서 출발해서 목적지(ay,ax)로 갈 수 있는 경로의 수
ay,ax를 토스트집의 좌표로 설정한 뒤 DP[1][1]을 구한 값,
ay,ax를 h,w로 설정한 뒤 DP[토스트집의 Y][토스트집의 X]를 구한 값을 곱하면 된다.

1000007로 계산시 나눠줘야 하며 위의 두 값을 곱할 때 int 범위를 넘어갈 수 있으므로
long long으로 계산해야 한다.

#include <cstdio>
#include <cstring>
using namespace std;
int w,h,mod=1000007,ax,ay,dp[201][201];

int sol(int y,int x){
    if(y==ay&&x==ax) return 1;

    int& ret = dp[y][x];
    if(ret!=-1) return ret;
    ret=0;
    if(y+1<=h) ret = sol(y+1,x);
    if(x+1<=w) ret += sol(y,x+1);
    return ret%=mod;
}
int main(){
    scanf("%d%d%d%d",&w,&h,&ax,&ay);

    memset(dp,-1,sizeof(dp));
    long long ans=sol(1,1);

    int sy=ay,sx=ax;
    ay=h,ax=w;

    memset(dp,-1,sizeof(dp));
    ans*=sol(sy,sx);
    
    printf("%lld",ans%mod);
}

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

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

[난이도] Gold3
[유형] DP

[풀이]
DP

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int N,dp[400][400][400],v,inf=-8e7,as,bs;
vector<int> arr[2];
int sol(int n,int a,int b){
    if(a==as||b==bs) return 0;
    int& ret = dp[n][a][b];
    if(ret!=inf) return ret;
    ret=sol(n+1,a+1,b+1)+arr[0][a]*arr[1][b];
    if(N>n+as-a) ret=max(ret,sol(n+1,a,b+1));
    if(N>n+bs-b) ret=max(ret,sol(n+1,a+1,b));
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int j=0;j<2;j++){
        for(int i=0;i<N;i++){
            scanf("%d",&v);
            if(v!=0) arr[j].push_back(v);
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++) dp[i][j][k]=inf;
    as=arr[0].size(),bs=arr[1].size();
    printf("%d",sol(0,0,0));
}

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