골드 그리디 랜덤 (2)

오늘도 열심히 그리디를 하자.

1. BOJ 2759 - 팬케이크 뒤집기 (G4)

http://boj.kr/2759

2759번: 팬케이크 뒤집기

 

sol) constructive(그리디 스타일)

자명하게도 n번 팬케이크가 n번 위치에 있지 않으면 반드시 n번 팬케이크를 1번으로 옮긴 후, n번으로 옮겨야 한다.

이렇게 옮기고 나면 n-1번 팬케이크가 n-1번 위치에 있는지 판별하는 문제로 바뀐다.

 

위 과정을 계속 반복하면 된다.

이때 1번 위치에서는 뒤집어도 상태가 똑같으므로 굳이 뒤집을 필요가 없다. 이를 고려하면 최악의 경우에도 2n-3번 이하로 뒤집게 된다.

#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 1000000007
ll n;
int main(){
    fast;
    ll t; cin>>t;
    while(t--){
        cin>>n;
        vector<ll> v(n), ans;
        for(auto &i : v)cin>>i;
        for(int i = n-1 ; i >= 0 ; i--){
            if(v[i]==i+1)continue;
            ll j;
            for(j = 0 ; j < n ; j++){
                if(v[j]==i+1)break;
            }
            if(j)ans.push_back(j+1);
            if(i)ans.push_back(i+1);
            reverse(v.begin(), v.begin()+j+1);
            reverse(v.begin(), v.begin()+i+1);
        }
        cout<<ans.size()<<" ";
        for(auto i : ans)cout<<i<<" "; cout<<"\n";
    }
}

 

2 - BOJ 17942 : 알고리즘 공부 (G1)

http://boj.kr/17942

골드 1 그리디가 왤케 많은지 모르겠다.

 

sol)파라메트릭 서치 + BFS or 그리디 + 탐색

그리디 풀이도 생각났지만 파라메트릭 풀이가 더 확실해 보여서 코드는 파라메트릭으로 풀었다.

 

일단 그리디 풀이는 다음과 같다.

먼저 공부량이 가장 작은 알고리즘은 들어가도 손해를 보지 않는다. 왜냐하면 나중에 공부량이 깎여서 나중에 가장 작은 알고리즘보다 더 작은 비용인 알고리즘이 생길 순 있지만, 그러한 알고리즘이 생기려면 공부량이 가장 작은 알고리즘 이상의 공부량을 요구하는 알고리즘이 필요하기 때문이다. 따라서 작은 알고리즘부터 넣으면서, 공부량이 깎이는 것을 모두 체크한 후 또 가장 작은 공부량을 넣는 과정을 우선순위 큐로 반복하면 된다.

 

파라메트릭 풀이는 다음과 같다.

f(x) := 공부량을 x 이하로만 구성할 때 m개 이상을 공부할 수 있는가? (bool)

f(x)는 다음과 같이 동작한다.

(1) 먼저 x 이하의 모든 알고리즘을 고른다.

(2) m 이상을 골랐다면 바로 true이고, 미만을 골랐다면 고른 알고리즘들을 모두 큐에 넣은 후, bfs로 탐색하면서 공부량을 감소시키고, x이하로 감소한 알고리즘들을 더 넣는다.

(3) (2)까지 끝났을 때 m 이상이면 true, 아니면 false를 리턴한다.

 

따라서 x에 대한 이분탐색을 통해 최적해를 구할 수 있다.

#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 1000000007
ll n, m;
vector<ll> v;
vector<pair<ll,ll>> adj[101010];
bool f(ll x){
    ll cnt = 0;
    vector<bool> sel(n, 0), visited(n,0);
    for(int i = 0 ; i < n ; i++)if(v[i]<=x)cnt++, sel[i]=1;
    if(cnt>=m)return 1;
    queue<ll> q;
    auto e = v;
    for(int i = 0 ; i < n ; i++)if(sel[i])q.push(i), visited[i]=1;
    while(q.size()){
        ll cur = q.front();
        q.pop();
        for(auto [next, w] : adj[cur]){
            e[next] -= w;
            if(e[next]<=x){
                if(visited[next])continue;
                visited[next]=1;
                q.push(next);
                sel[next]=1;
                cnt++;
            }
        }
    }
    return cnt>=m;
}
int main(){
    fast;
    cin>>n>>m;
    v.resize(n); for(auto &i : v)cin>>i;
    ll k; cin>>k;
    while(k--){
        ll a,b,c; cin>>a>>b>>c; a--; b--;
        adj[a].push_back({b,c});
    }
    ll l = -1, r = 1e8+1;
    while(l+1 < r){
        ll mid = l+r>>1;
        if(f(mid))r = mid;
        else l = mid;
    }
    cout<<r;
}

 

3. BOJ 2405 - 세 수, 두 M (G4)

http://boj.kr/2405

2405번: 세 수, 두 M

그나마 쉬운(?) 그리디이다. 사실 그리디는 모두 어렵다

 

sol) 그리디

일반성을 잃지 않고 세 수 a,b,c(a>=b>=c)를 골랐다고 하자. 이를 위해 배열은 정렬했다고 가정하자.

이때 최대화해야하는 값은 $$|b-\frac{a+b+c}{3}|$$ 이다. 

이때 차이의 3배를 출력해야 하므로 식을 정리하면 $$|2b-a-c|$$ 가 된다.

이제 이 식의 최댓값을 구해야하는데, 먼저 절댓값의 성질에 따라 2b-a-c와 a+c-2b로 나뉜다.

 

(i)2b-a-c

c는 가장 작은 값을 고르면 되고, b<=a이므로 a는 b 바로 뒤의 수가 되면 2b-a가 최대이다.

즉 b를 정할때마다 a의 최적값은 자동으로 결정되므로 O(N)에 2b-a의 최댓값을 구할 수 있고, 2b-a-c의 최댓값을 구할 수 있다.

 

(ii)a+c-2b

(i)과 비슷하게 c를 정할 때마다 b의 최적값이 자동 결정되고, a는 가장 큰 값을 고르면 된다. O(N)에 a+c-2b의 최댓값을 구할 수 있다.

 

시간복잡도는 정렬이 지배하므로 O(NlogN)이 된다.

#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 1000000007
ll n;
int main(){
    fast;
    cin>>n;
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    sort(all(v));
    ll ans = -1e18;
    for(int i = 1 ; i < n-1 ; i++){
        ans = max(ans, 2*v[i]-v[i+1]);
    }
    ll res = ans-v[0];
    ans = -1e18;
    for(int i = 0 ; i < n-2 ; i++){
        ans = max(ans, v[i]-2*v[i+1]);
    }
    res = max(res, ans+v.back());
    cout<<res;
}

 

사실 2759는 2번 틀리고 맞았다

슬슬 머리아파