USACO 2023 February Contest Bronze 문제풀이 정리
Hungry Cow
-
건초더미가 d[i]일에 b[i] 개 씩 들어올때, T일까지 먹을 수 있는 건초더미 개수
- T에 대해 bruteforce 를 해보려고 했지만, $ T <10^14$ 이므로 불가능
- N에 대해 d[i]-d[i-1] 과 b[i-1]+left 를 비교하면서 풀이 가능
- $O(N)$ Time complexity
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
cin.tie(0)->sync_with_stdio(0);
ll N, T;
cin >> N >> T;
vector<ll> d(N+1),b(N+1);
for(int i = 0;i<N;i++) cin >> d[i] >>b[i];
d[N] = T+1; b[N] = 0;
ll cnt = 0, left = 0;
for(int i = 1 ;i<=N;i++){
cnt += min(d[i]-d[i-1], b[i-1]+left);
left = (d[i]-d[i-1]<b[i-1]+left) ? left+b[i-1] -(d[i]-d[i-1]):0;
}
cout << cnt <<"\n";
}
Stamp Grid
- 시뮬레이션 문제
- $O(4*(N-K+1)^2 K^2)$ Time Complexity
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
int T; cin >> T;
while(T--){
bool canvas[20][20], stamp[4][20][20], cmp[20][20];
memset(canvas, false, sizeof(canvas));
memset(cmp,false, sizeof(cmp));
memset(stamp,false,sizeof(stamp));
int N, K;
cin >> N;
for(int i = 0; i<N;i++){
for(int j = 0; j<N;j++){
char c; cin >> c;
if(c == '*') canvas[i][j] = true;
}
}
cin >> K;
for(int i = 0; i<K;i++){
for(int j = 0; j<K;j++){
char c; cin >> c;
if(c == '*') stamp[0][i][j] = true;
}
}
for(int t = 1; t<4;t++){
for(int i = 0; i<K;i++){
for(int j = 0; j<K;j++){
stamp[t][j][K-1-i] = stamp[t-1][i][j];
}
}
}
for(int t = 0; t<4 ; t++){
for(int i = 0; i<N-K+1;i++){
for(int j = 0; j<N-K+1;j++){
bool f = true;
for(int x = 0; x<K;x++){
for(int y = 0; y<K;y++){
if(!canvas[i+x][j+y] && stamp[t][x][y]) f = false;
}
}
if(f){
for(int x = 0; x<K;x++){
for(int y = 0; y<K;y++){
if(stamp[t][x][y]) cmp[i+x][j+y] = true;
}
}
}
}
}
}
bool f = true;
for(int i = 0; i<N;i++){
for(int j = 0;j<N;j++){
if(cmp[i][j] != canvas[i][j]) f = false;
}
}
cout << (f ? "YES" : "NO")<<"\n";
}
}
Watching Mooloo
- greedy 문제
- 처음에는 1+K 를 비용으로 내고, 그다음부터는 d[i]-d[i-1] 만큼 연장할지, 새로 1+K를 낼지 둘중 최소를 내면서 풀면된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
ll N, K,ans = 0;
vector<ll> d(N);
for(auto &i : d) cin >> i;
for(int i = 0; i<N;i++){
if(i == 0)ans += K+1;
else ans += min(d[i]-d[i-1], K+1);
}
cout << ans <<"\n";
}