그리디 연습이 좀 필요하다고 느껴서 랜덤으로 그리디 문제를 풀어봤다.
1. BOJ 20311 : 화학 실험 (G5)
20311번: 화학 실험
화학 실험을 하던 윤이는 일렬로 나열해 놓은 $N$개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이
www.acmicpc.net
solve) 그리디(sort) + constructive
꽤나 직관적인 그리디 문제이다. 색깔 수가 많은 숫자부터 배치하는데, 앞쪽부터 1칸씩 띄워서 배치하면 된다. 이때 배치하다가 갯수가 부족하면 다음 색깔부터 이어서 배치하되, 다른 색깔은 인접해도 무방하므로 다음과 같이 배치한다.
예를 들어 1번 색과 2번 색을 배치한다고 가정하자. (0은 비어있다)
1 0 1 0 1 0 0 0
이 상태에서 2번을 색칠할 때는,
1 0 1 0 1 2 0 2
이런식으로 인접하게 배치한다.
1 2 1 2 1 2 0 2
그 후 이렇게 앞에서부터 비어있는 칸을 채우면 된다.
비어있는 칸을 배치하다가 인접한 색이 같으면 불가능한 경우이다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
ll fill_idx = 1;
ll cur_idx = 1;
ll n, k;
ll ans[303030];
priority_queue<pair<ll,ll>> pq;
int main(){
fast;
cin>>n>>k;
for(int i = 1 ; i <= k ; i++){
ll a; cin>>a;
pq.push({a,i});
}
while(pq.size()){
auto [cur, color] = pq.top();
pq.pop();
for(; fill_idx <= n ;){
if(cur==0)break;
ans[fill_idx] = color;
cur--;
if(cur)fill_idx+=2;
} fill_idx++;
while(cur>0){
if(ans[cur_idx]!=0){
cur_idx++;
continue;
}
if(ans[cur_idx-1] == color or ans[cur_idx+1] == color)return cout<<-1, 0;
ans[cur_idx] = color;
cur--;
cur_idx++;
}
}
for(int i = 1 ; i <= n ; i++)cout<<ans[i]<<" ";
}
2. BOJ 3430 - 용이 산다 (G1)
solve)그리디(PQ)
흥미로운 문제이다. 데드라인 형식으로 생각해보자.
어떤 숫자 k가 i와 j 2군데에서만 쿼리가 들어온다고 해보자.
이때 다음과 같은 결론을 도출할 수 있다.
1. [1,i-1]번 사이 쿼리에서 적어도 한 번은 k를 비워주어야 한다.
2. [i+1, j-1]번 사이 쿼리에서 적어도 한 번은 k를 비워주어야 한다.
i+1번부터 시작하는 이유는 만약 i 이전에 비운다면, i 쿼리에서 다시 물을 채우게 되므로 의미가 없기 때문이다.
따라서, 같은 숫자의 쿼리들끼리 구간을 지정한 후, 그 구간에서 한번만 물을 비우도록 하면 된다.
쿼리가 [l, r] 형태라고 하자.
이러한 숫자가 여러개 있으므로, 각 쿼리마다 구간을 지정한 후, i번째 쿼리에는 l=i인 모든 쿼리를 min heap에 {r, k} (k는 비워야 하는 호수 위치) 형태로 넣어주고, 중간에 호수가 차 있는지를 잘 판별하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
ll t;
typedef pair<ll,ll> P;
vector<P> v[1010101];
int main(){
fast;
cin>>t;
while(t--){
ll n, m; cin>>n>>m;
vector<ll> query(m), lastidx(n+1, 0);
for(auto &i : query)cin>>i;
vector<bool> isfill(n+1, 1);
priority_queue<P, vector<P>, greater<P>> pq;
for(int i = 0 ; i < m ; i++)v[i].clear();
for(int i = 0 ; i < m ; i++){
if(query[i]>0){
ll s = lastidx[query[i]];
ll e = i;
ll idx = query[i];
v[s].push_back({e, idx});
lastidx[query[i]] = i+1;
}
}
bool f = 1;
vector<ll> ans;
for(int i = 0 ; i < m ; i++){
for(auto [a,b] : v[i])pq.push({a,b});
if(query[i]==0){
if(pq.empty()){
ans.push_back(0);
continue;
}
auto [a,b] = pq.top();
pq.pop();
if(!isfill[b]){
f=0;
break;
}
isfill[b]=0;
ans.push_back(b);
}
else{
if(isfill[query[i]]){
f=0;
break;
}
isfill[query[i]]=1;
}
}
if(!f)cout<<"NO\n";
else{
cout<<"YES\n";
for(auto i : ans)cout<<i<<" ";
cout<<"\n";
}
}
}
3. BOJ 1352 - 문자열 (G1)
아니 랜디를 돌렸는데 G5 G1 G1이 말이 되냐
solve)그리디 + 백트래킹
정말 특이하게 푼 것 같다. 먼저 A,B,C,D..가 몇번 나올지를 처음 위치를 통해 정해주어야 한다.
A는 자명하게 1번 위치에 있어야 한다.
B는 자명하게 2번 위치에 있어야 한다.
C는 3번 위치에 있거나 4번 위치에 있을 수 있다. (ABBC, ABCBC ...)
D는 4번 위치부터 8번 위치 사이에 있을 수 있다. (여기부터는 왜 그런지 직접 생각해보자. 이전까지의 합이 최대 7임을 이용하면 유도된다)
...
즉 i번째 문자(ABC 사전순)은 i~2^(i-1) 사이의 위치에 들어가야 하는 것이다.
이때 당연히 앞쪽 문자의 수가 많을 수록 이득임을 알 수 있다.
또한 처음 위치를 정했다면 문자의 갯수가 자동으로 결정되므로, n에 맞춰 A,B,C,D..의 개수를 지정해야 한다.
예를 들어 A=1,B=2,C=3 위치에 있을 때 1+2+3=6이므로 자릿수가 반드시 6이다. ex)ABCBCC
따라서 백트래킹으로 i번 문자의 위치를 정해주는데, 큰 수부터 가능한지 확인하면서 정해주고 완성되었다면 백트래킹을 바로 중단한다.
그 후 문자열에 사전순으로 잘 넣어주면 문제를 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
ll sel[16];
vector<vector<ll>> v;
void backtrack(ll x, ll i){
if(v.size())return;
if(x==0){
vector<ll> e;
for(int i = 1 ;; i++){
if(sel[i]<0)break;
e.push_back(sel[i]);
}
v.push_back(e);
return;
}
for(int j = pow(2,i-1) ; j >= i ; j--){
if(x-j>=0){
if(sel[i-1]>j)break;
bool f = 1;
for(int k = 1 ; k <= i ; k++)if(sel[k]==j){
f=0;
break;
}
if(!f)continue;
sel[i] = j;
backtrack(x-j, i+1);
sel[i] = -1;
}
}
}
int main(){
memset(sel, -1, sizeof(sel));
ll n; cin>>n;
backtrack(n, 1);
ll sum = 0;
string ans;
for(int i = 0 ; i <= n ; i++)ans += 'Z';
for(auto X : v){
memset(sel, -1, sizeof(sel));
for(int i = 1 ; i <= X.size() ; i++)sel[i] = X[i-1];
string res;
for(int i = 0 ; i <= n ; i++)res += '#';
for(int i = 1 ; i <= X.size() ; i++){
res[sel[i]] = 'A'+i-1;
sel[i]--;
}
ll idx = 1;
string ret="";
for(int i = 1 ; i <= n ; i++){
if(res[i]=='#'){
while(sel[idx]<=0){
if(sel[idx]<0)break;
idx++;
}
sel[idx]--;
res[i] = 'A'+idx-1;
}
ret += res[i];
}
if(ans>ret)ans = ret;
}
if(ans[0]=='Z')cout<<-1;
else cout<<ans;
}
그리디 너무 어려워요
'백준 > 랜디' 카테고리의 다른 글
| 골드 그리디 랜덤 (2) (0) | 2023.06.20 |
|---|
