2020. 10. 2. 00:02ㆍPS/BaekJoon Practice
DP 위주로 2시간 동안 연습한 세트이다.
1. 카드 구매하기2 (Silver 1)
16194번: 카드 구매하기 2
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
그냥 쉬운 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)
2616번: 소형기관차
첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있�
www.acmicpc.net
문제 지문이 읽기 싫게(?) 보여서 거르려다가 푼 문제.
진짜 쉽다.
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)
2629번: 양팔저울
첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무
www.acmicpc.net
백트래킹에 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)
1328번: 고층 빌딩
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼��
www.acmicpc.net
골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) (진행중)
1086번: 박성원
첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.
www.acmicpc.net
아직 풀지는 못했으나 Bit DP 인거 같아서 언젠가 각 잡고 시도해볼 예정.

'PS > BaekJoon Practice' 카테고리의 다른 글
알고리즘 공부 : LIS (0) | 2020.12.25 |
---|---|
백준 재활 연습 - 1일차 (1) | 2020.11.18 |
백준 연습 #2 (0) | 2020.10.02 |