USACO 2023 February Contest, Bronze
1. 배고픈 소 (Hungry Cow)
매일 저녁에 소 베시(베시)는 창고에 건초가 있으면 한 개의 건초를 먹는다. 농부 존은 베시가 배고픈思いをしない 있도록 특정 날짜에 건초를 배달한다. 구체적으로, 날짜 di에 bi개의 건초가 아침에 배달된다. 첫 번째 T일까지 베시가 먹을 건초의 총 개수를 계산하는 문제이다.
문제 분석
각 날짜에 대해 두 가지 경우를 고려해야 한다:
- 건초가 부족한 경우: 베시가 먹는 날 수는 현재 보유한 건초의 수와 같다.
- 건초가 충분한 경우: 다음 배달일까지의 일수만큼 먹을 수 있으며, 남은 건초가 생길 수 있다.
풀이 접근법
배달 사이의 간격과 현재 건초 수를 비교하면서 진행한다. 현재 구간의 건초가 다음 배달일까지의 일수보다 많으면 남은 건초를 다음 구간으로 이월한다.
#include
using namespace std;
int main() {
long long n, T;
cin >> n >> T;
vector<long long> day(n + 2);
vector<long long> hay(n + 2);
for (int i = 1; i <= n; i++) {
cin >> day[i] >> hay[i];
}
day[n + 1] = T + 1;
long long result = 0;
long long carry = 0;
for (int i = 1; i <= n; i++) {
long long interval = day[i + 1] - day[i];
if (hay[i] + carry >= interval) {
carry = hay[i] + carry - interval;
result += interval;
} else {
result += hay[i] + carry;
carry = 0;
}
}
cout << result << endl;
return 0;
}
2. 스탬프 그리드 (Stamp Grid)
N×N 캔버스에 특정 셀에만 검은색 잉크가 있는 스탬프 그림을 만드는 문제이다. 베시에게는 K×K 크기의 스탬프가 주어지고, 스탬프는 90도 회전시켜 사용할 수 있다. 스탬프로涂った 셀은 다시 되돌릴 수 없다. 목표 그림을 얻을 수 있는지를 판단하는 문제이다.
문제 분석
핵심 포인트:
- 스탬프를 놓을 때마다 ".*"가 아닌 "*"만 덮어쓸 수 있다
- 회전 방향(시계/반시계)은 결과에 영향을 주지 않음
- 스탬프를 놓는 순서도 결과에 영향을 주지 않음
따라서 모든 가능한 위치와 회전 방향에 대해 스탬프를 놓아보고 목표 그림과 일치하는지 확인하면 된다.
#include
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<string> target(N);
for (int i = 0; i < N; i++) cin >> target[i];
int K;
cin >> K;
vector<string> stamp(K);
for (int i = 0; i < K; i++) cin >> stamp[i];
vector<string> canvas(N, string(N, '.'));
auto rotateStamp = [&](vector<string>& s) {
vector<string> temp(K, string(K, ' '));
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
temp[i][j] = s[K - 1 - j][i];
}
}
s = temp;
};
auto tryStamp = [&](const vector<string>& s) {
for (int rot = 0; rot < 4; rot++) {
vector<string> current = stamp;
for (int r = 0; r < rot; r++) {
rotateStamp(current);
}
for (int i = 0; i <= N - K; i++) {
for (int j = 0; j <= N - K; j++) {
bool valid = true;
for (int x = 0; x < K && valid; x++) {
for (int y = 0; y < K && valid; y++) {
if (target[i + x][j + y] == '.' && current[x][y] == '*') {
valid = false;
}
}
}
if (valid) {
for (int x = 0; x < K; x++) {
for (int y = 0; y < K; y++) {
if (current[x][y] == '*') {
canvas[i + x][j + y] = '*';
}
}
}
}
}
}
}
};
tryStamp(stamp);
bool success = true;
for (int i = 0; i < N && success; i++) {
for (int j = 0; j < N; j++) {
if (target[i][j] != canvas[i][j]) {
success = false;
break;
}
}
}
cout << (success ? "YES" : "NO") << endl;
}
return 0;
}
3. 무루 시청 (Watching Mooloo)
N일 동안 무루(Mooloo)를 시청할 계획이 있다. 구독 시스템은 d일 연속 구독에 d+K비용이 든다. 각 구독은 언제든 시작할 수 있고, 현재 구독이 만료되면 새 구독을 시작할 수 있다. 시청 일정을 충족하는 최소 비용을 구하는 문제이다.
문제 분석
이 문제는 전형적인 그리디 알고리즘 문제이다. 각 시청일에 대해 두 가지 선택지가 있다:
- 이전 구독과 연결: K + 1 + (di - di-1) 비용
- 새 구독 시작: K + 1 비용
di - di-1과 K+1 중 더 작은 값을 선택하면 된다. 이는 각 결정이 이후 결정에 영향을 주지 않기 때문에 국소 최적해가 전체 최적해가 된다.
#include
using namespace std;
int main() {
long long N, K;
cin >> N >> K;
vector<long long> day(N + 1);
for (int i = 1; i <= N; i++) {
cin >> day[i];
}
long long total = K + 1;
for (int i = 2; i <= N; i++) {
long long gap = day[i] - day[i - 1];
total += min(gap, K + 1);
}
cout << total << endl;
return 0;
}