백준 연습 #1

DP 위주로 2시간 동안 연습한 세트이다.

 

1. 카드 구매하기2 (Silver 1)

www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

그냥 쉬운 DP 문제.

dp[i]=min(dp[i],dp[j]+su[i-j]);

#include <bits/stdc++.h>
#define MEM 1009
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
ll n;
ll su[MEM], dp[MEM];
main() {
    sanic;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> su[i];
    for(int i=1; i<=n; i++)
        dp[i] = 1e9+7;
    for(int i=1; i<=n; i++)
        for(int j=0; j<i; j++)
            dp[i]=min(dp[i],dp[j]+su[i-j]);
    cout << dp[n];
}

2. 소형 기관차(Gold 4)

www.acmicpc.net/problem/2616

2616번: 소형기관차

문제 지문이 읽기 싫게(?) 보여서 거르려다가 푼 문제.

진짜 쉽다.

dp[i][j] = i번 소형기관차에 j-m+1~j번까지의 객차를 끌고 갈때 답

prefix sum을 이용해서 객차의 고객 수를 구해주면, 식은 이렇게 나온다. 런타임 에러에 주의해서 for문을 돌리는 것을 주의하자.

dp[i][j] = max(dp[i][j-1], (p[j]-p[j-m])+dp[i-1][j-m]);

#include <bits/stdc++.h>
#define MEM 55555
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
ll n,m;
ll p[MEM], dp[4][MEM];
main() {
    sanic;
    cin >> n;
    for(int i=1; i<=n; i++){
        ll q;
        cin >> q;
        p[i] += p[i-1]+q;
    }
    //for(int i=1; i<=n; i++)
      //  cout << p[i] << ' ';
    //cout << '\n';
    cin >> m;
    for(int i=1; i<=3; i++)
        for(int j=m*i; j<=n; j++)
            dp[i][j] = max(dp[i][j-1], (p[j]-p[j-m])+dp[i-1][j-m]);
    cout << dp[3][n];
}

3. 양팔저울 (Gold 3)

www.acmicpc.net/problem/2629

2629번: 양팔저울

백트래킹에 DP를 섞은 문제.

문제 이해 때문에 잘못 나온거로 인해서 시간을 많이 뺏어먹었다. 이런ㅆ

#include <bits/stdc++.h>
#define MEM 15555
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
ll n,m;
ll p[MEM], dp[32][MEM];
void bt(ll a, ll b){
    if(a>n) return;
    if(dp[a][b]) return;
    dp[a][b] = 1;
    bt(a+1, b+p[a]);
    bt(a+1, b);
    bt(a+1, abs(b-p[a]));
}
main() {
    sanic;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> p[i];
    bt(0, 0);
    ll t;
    cin >> t;
    while(t--){
        ll q;
        cin >> q;
        cout << (dp[n][q] ? "Y":"N") << ' ';
    }
}

4. 고층 건물 (Gold 1)

www.acmicpc.net/problem/1328

1328번: 고층 빌딩

골1 치고는 쉬운 문제인듯 하다.

dp[i][j][k] = i개의 건물 중 j개가 오른쪽, k가 왼쪽에 있을 때 해

세가지 경우를 생각할 수 있는데

i) dp[i-1][j][k]

건물 높이가 1인 것을 최대 i-2칸 넣을 수 있다. 

ii) dp[i-1][j-1][k]

왼쪽 하나 추가한 것.

iii) dp[i-1][j][k-1]

오른쪽 하나 추가한 것.

 

그러므로 식은

dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k]+dp[i-1][j][k-1]

#include <bits/stdc++.h>
#define MEM 155
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll n,m,k;
ll dp[MEM][MEM][MEM];
main() {
    sanic;
    cin >> n >> m >> k;
    dp[1][1][1] = 1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int l=1; l<=k; l++){
                dp[i][j][l] += dp[i-1][j][l]*(i-2);
                dp[i][j][l] += dp[i-1][j-1][l]+dp[i-1][j][l-1];
                dp[i][j][l] %= MOD;
            }
        }
    }
    cout << dp[n][m][k];
}

5. 박성원 (Platinum 5) (진행중)

www.acmicpc.net/problem/1086

1086번: 박성원

아직 풀지는 못했으나 Bit DP 인거 같아서 언젠가 각 잡고 시도해볼 예정.

 

스코어보드