티스토리 뷰
$D$
더보기
이 문제는 $n$명의 고객이 크리스마스 트리를 구매하려고 할 때, 상점이 모든 트리에 대해 동일한 가격을 설정하여 최대 수익을 얻는 방법을 찾는 문제이다. 각 고객은 두 개의 가격 한계값 $a_i$와 $b_i$를 가지며, 가격이 $a_i$ 이하이면 긍정적인 리뷰를 남기고, $b_i$ 이하이면 부정적인 리뷰를 남긴 채 구매하며, $b_i$를 초과하면 구매하지 않는다. 상점은 최대 $k$개의 부정적인 리뷰를 허용하면서 최대 수익을 얻을 수 있는 트리의 가격을 결정해야 한다.
간단한 에디토리얼
이 문제는 고객별 가격 임계값 a와 b를 이용해, 하나의 가격을 설정했을 때 얻을 수 있는 총 수익을 계산하는 문제이다. 가능한 후보 가격은 a와 b의 집합에 한정되며, 스위프 라인 기법을 통해 이벤트를 처리하면서 구매 고객 수(cnt)와 부정 리뷰 수(bad)를 업데이트하여 최대 수익(ans)을 효율적으로 구한다.
1. 기본 설정 및 테스트 케이스 처리
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
// 각 테스트 케이스별로 고객 수 n, 허용 부정 리뷰 k를 입력받음.
// ...
}
2. 입력 및 이벤트 배열 생성
vector<int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
vector<pair<int, int>> ev;
for (int i = 0; i < n; ++i) {
ev.emplace_back(a[i], 1);
ev.emplace_back(b[i], 2);
}
- a, b 배열을 읽은 후, 고객 i에 대해 두 이벤트 (a[i], 1)과 (b[i], 2)를 생성한다.
3. 이벤트 정렬
sort(ev.begin(), ev.end());
- 모든 이벤트를 가격 기준 오름차순으로 정렬한다.
4. 스위프 라인 처리 및 최대 수익 계산
long long ans = 0;
int cnt = n, bad = 0;
for (int i = 0; i < 2 * n;) {
auto [x, y] = ev[i];
if (bad <= k)
ans = max(ans, x * 1LL * cnt);
while (i < 2 * n && ev[i].first == x) {
bad += (ev[i].second == 1);
bad -= (ev[i].second == 2);
cnt -= (ev[i].second == 2);
++i;
}
}
- 현재 가격 x에서 부정 리뷰 수(bad)가 k 이하이면, x × 현재 구매 고객 수(cnt)를 최대 수익 후보로 갱신한다.
- 같은 가격 x를 가진 이벤트들을 한꺼번에 처리하면서:
- 타입 1 이벤트(가격 초과 시 부정 리뷰 발생)는 bad를 증가시킨다.
- 타입 2 이벤트(가격 초과 시 구매 포기)는 bad를 감소시키고, cnt도 감소시킨다.
5. 결과 출력
cout << ans << '\n';
$E$
더보기
이 문제는 $n$개의 카드로 이루어진 덱에서 특정 위치의 조커(Joker) 카드가 $q$번의 연산 후에 위치할 수 있는 서로 다른 위치의 개수를 구하는 문제이다. 각 연산에서는 지정된 위치의 카드를 덱의 맨 앞이나 맨 뒤로 이동시킬 수 있다.
초기 세그먼트 설정
vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
- 중앙 세그먼트: [m, m]
- 좌/우 세그먼트: 초기엔 비활성 상태로, 나중에 활성화
연산 처리 및 세그먼트 업데이트
while (q--) {
int x;
cin >> x;
bool ins = false;
for (auto& [l, r] : segs) {
if (x < l)
l = max(1, l - 1);
else if (x > r)
r = min(n, r + 1);
else {
ins = true;
if (l == r)
l = n + q, r = -q;
}
}
if (ins) {
segs[0] = {1, max(segs[0].second, 1)};
segs[2] = {min(segs[2].first, n), n};
}
// ...
}
- x < l: 세그먼트 좌측 이동 → [l-1, r]
- x > r: 세그먼트 우측 이동 → [l, r+1]
- l ≤ x ≤ r: 내부에서 분리 → ins 플래그 활성화; 단일 원소면 비활성화
가능한 위치 개수 계산
int lf = 0, rg = -1, ans = 0;
for (auto [l, r] : segs) {
if (l > r) continue;
if (l > rg) {
ans += max(0, rg - lf + 1);
lf = l; rg = r;
}
rg = max(rg, r);
}
ans += max(0, rg - lf + 1);
cout << ans << ' ';
- 각 활성 세그먼트의 합집합 길이(조커가 있을 수 있는 위치 수)를 계산
전체 흐름
- 각 연산마다 세그먼트를 업데이트하여 조커 위치 범위를 변경
- 업데이트된 범위의 총 길이를 출력하여 가능한 위치 개수를 구함
$F$
더보기
- $1×10^9$ 크기의 일렬 셀에 $n$개의 스네이크를 서로 겹치지 않게 배치한다.
- 게임은 $q$초 동안 진행되며, 매초 한 스네이크가 늘어나거나 줄어드는 이벤트가 발생한다.
- 이벤트 중 스네이크가 다른 스네이크와 충돌하거나 필드 끝에 도달하면 패배한다.
- 모든 이벤트를 성공적으로 수행하면, 최종 점수는 스네이크가 차지한 최대 셀 번호가 된다.
- 목표는 충돌 없이 게임을 진행하며 얻을 수 있는 최소 점수를 구하는 것이다.
int n, q;
vector<int> id, ch;
bool read() {
if (!(cin >> n >> q))
return false;
id.resize(q);
ch.resize(q);
fore (i, 0, q) {
char c;
cin >> id[i] >> c;
id[i]--; // 스네이크 번호를 0-indexed로 변경
ch[i] = c == '+' ? 1 : -1;
}
return true;
}- 목적:
- n: 스네이크의 개수,
- q: 이벤트의 총 개수를 입력받습니다.
- 구현:
- id 벡터는 각 이벤트가 어느 스네이크에 해당하는지 저장합니다.
- ch 벡터는 이벤트의 종류를 저장하는데, '+'이면 1 (enlarge), '-'이면 -1 (shrink)로 저장합니다.
- 주의:
- 스네이크 번호를 0부터 시작하도록 조정합니다.
2. 두 스네이크 간 최소 거리 계산 함수 (getDist 함수)
int getDist(int s, int t) {
int pSum = 0, cMin = 0;
fore (e, 0, q) {
if (id[e] == t)
pSum += ch[e] < 0; // t번 스네이크가 shrink 이벤트이면 gap이 1 증가
if (id[e] == s)
pSum -= ch[e] > 0; // s번 스네이크가 enlarge 이벤트이면 gap이 1 감소
cMin = min(cMin, pSum);
}
return -cMin + 1;
}- 목적:
- 스네이크 s를 왼쪽, 스네이크 t를 오른쪽에 놓았을 때, 게임 중 두 스네이크 간의 간격(초기 gap)을 얼마나 벌어야 하는지 계산합니다.
- 아이디어:
- 각 이벤트마다, t번 스네이크가 줄어들면 (shrink) gap이 늘어나고, s번 스네이크가 늘어나면 (enlarge) gap이 줄어듭니다.
- 게임 진행 중 gap이 음수가 되면 충돌하므로, 모든 이벤트 동안 **gap + (누적 변화량)**가 0 이상이어야 합니다.
- 따라서, 누적 변화량의 최솟값(cMin)을 찾고, 그 절댓값에 1을 더한 값이 두 스네이크 사이에 필요한 최소 간격입니다.
3. 동적 계획법 (Bitmask DP)로 최적 순서 찾기 (solve 함수)
inline void solve() {
vector<vector<int>> minDist(n, vector<int>(n, INF));
fore (i, 0, n) fore (j, 0, n)
minDist[i][j] = getDist(i, j);- minDist 배열 계산:
- 각 minDist[i][j]는 스네이크 i가 왼쪽, 스네이크 j가 오른쪽에 놓였을 때 필요한 최소 간격을 저장합니다.
- 모든 가능한 쌍에 대해 getDist(i, j)를 호출합니다.
vector<int> len(n, 0);
fore (e, 0, q)
len[id[e]] += ch[e] > 0;- len 배열 계산:
- 각 스네이크가 enlarge 이벤트를 받은 횟수를 저장합니다.
- 최종 점수를 계산할 때, 마지막 스네이크의 enlarge 횟수를 더해야 하므로 필요합니다.
vector< vector<int> > d(1 << n, vector<int>(n, INF));
fore (i, 0, n)
d[1 << i][i] = 1;- 초기 DP 상태 설정:
- d[mask][lst]는 현재 mask에 해당하는 스네이크들이 배치되었을 때, 마지막 배치된 스네이크가 lst인 상태에서의 오른쪽 끝 셀 번호(최소값)를 나타냅니다.
- 처음에는 각 스네이크를 개별로 배치할 때 위치를 1 (가장 왼쪽)로 두고 초기화합니다.
fore (mask, 1, 1 << n) fore (lst, 0, n) {
if (d[mask][lst] == INF)
continue;
fore (nxt, 0, n) {
if ((mask >> nxt) & 1)
continue;
int nmask = mask | (1 << nxt);
d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
}
}- DP 전이:
- 현재 배치된 스네이크 집합 mask와 마지막 스네이크 lst가 있을 때, 아직 배치되지 않은 스네이크 nxt를 오른쪽에 놓는 경우를 고려합니다.
- minDist[lst][nxt]만큼의 거리를 추가하여 새 상태 d[nmask][nxt]를 업데이트합니다.
- 모든 스네이크가 배치될 때까지 (mask가 모든 스네이크를 포함할 때까지) 반복합니다.
int ans = INF;
fore (lst, 0, n)
ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
cout << ans << endl;
}- 최종 답 계산:
- 모든 스네이크가 배치된 상태 (mask == (1<<n)-1)에서, 각 마지막 스네이크 lst에 대해 d[mask][lst]에 해당 스네이크의 enlarge 횟수 len[lst]를 더합니다.
- 이 값이 최종 점수이며, 최소 점수를 출력합니다.
4. main 함수
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}- 역할:
- read() 함수를 통해 입력을 받고, 입력이 성공하면 solve() 함수를 호출하여 문제를 해결합니다.
요약
- 입력 처리: 스네이크 수와 이벤트 수, 각 이벤트의 스네이크 번호 및 종류를 읽음.
- 최소 간격 계산: getDist 함수를 통해 두 스네이크 사이에 필요한 최소 간격을 계산.
- 동적 계획법: Bitmask DP를 사용하여 스네이크를 최적 순서대로 배치하며, 각 상태에서 오른쪽 끝 셀의 최소값을 구함.
- 최종 점수: 모든 스네이크가 배치된 후, 마지막 스네이크의 enlarge 횟수를 더하여 최종 점수를 도출.