KOI 2016 고등부 전체 풀이

BOJ 13302 고등부 1번 리조트 

문제 링크 : https://www.acmicpc.net/problem/13302

문제 태그 

DP

문제 풀이

각 주어진 상황에서 여러가지 조건 중 하나를 선택할 수 있으며, 선택을 통해서 최적의 결과를 얻어내야 하는 문제. -> 아무리 봐도 DP. 각 상태는 DP table에 저장하고, 선택할 수 있는 조건들은 DP 관계식으로써 표현할 수 있다. 

dp[i][j]를 i번째날 쿠폰을 j개 들고 있을 때, 사용한 돈의 최솟값 이라고 설정하면, 1일권을 산 경우, 3일권을 산 경우, 5일 권을 산 경우, 쿠폰을 쓴 경우에 대해서 각각 일수와 쿠폰 수의 변화를 생각하여 DP식 들을 여러개 만들어 주면 된다. 자세한 것은 아래의 코드를 참고하자.

평가 : 난이도는 확실히 어렵지 않은 편이지만, 1번에 DP가 나온것 만으로도 잘못하면 시간을 훅 날릴 수 있는 위험한 대회였다고 생각한다. 제한이 오히려 작아서 함정에 걸리기 쉬운 문제라고 생각한다.  

코드

#include<bits/stdc++.h>
using namespace std;
int dp[303][606];
int arr[303];
#define inf 1000000009
int main()
{
    int i,j,k,l,m,n;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&k);
        arr[k]=1;
    }
    for(i=0;i<=n;i++)
        for(j=0;j<=5*n;j++)
            dp[i][j]=inf;
    dp[0][0]=0;
    for(i=1;i<=n;i++)
        for(j=0;j<=i;j++)
        {
            if(arr[i]==1)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
                if(i>=3&&j>=1)
                    dp[i][j]=min(dp[i][j],dp[i-3][j-1]+25000);
                if(i>=5&&j>=2)
                    dp[i][j]=min(dp[i][j],dp[i-5][j-2]+37000);
                dp[i][j]=min(dp[i][j],dp[i-1][j+3]);
            }
            else
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j]+10000);
                if(i>=3&&j>=1)
                    dp[i][j]=min(dp[i][j],dp[i-3][j-1]+25000);
                if(i>=5&&j>=2)
                    dp[i][j]=min(dp[i][j],dp[i-5][j-2]+37000);
                dp[i][j]=min(dp[i][j],dp[i-1][j+3]);
            }
        }
    int mini=inf;
    for(i=0;i<=n;i++)
    {
        mini=min(mini,dp[n][i]);
    }
    printf("%d",mini);
}

BOJ 13308 고등부 2번 주유소

문제 링크 : https://www.acmicpc.net/problem/13308

문제 태그

dijkstra

문제 풀이

그래프가 있고 1번 노드에서 n번 노드로 이동하는 데 드는 최소비용. 이거 완전 다익문제아님? 이라고 생각할 수 있는 여지가 많다. 하지만 기름 가격이라는 요소의 도입으로 그냥 다익으로 풀기는 어려워 보인다. 

다익에서 저장하고 있는 값들은 무엇일까? 그 노드에 도달할 때 까지의 최소거리(비용)이다. 어떤 점에 도달했으면 상태는 항상 똑같고, 이때까지 최소한의 비용으로 온 것이 항상 최선이기 때문이다. 

이 문제에 대해서 생각하자. 어떤 노드에 도착했을 때 중요한 요소는 지금까지 오는데 까지의 거리와 기름값이다. 지나쳐온 노드 중 최소 기름값으로 앞으로 이동할 것이기 때문에 어떤 기름값을 사용하여 도착했는지가 중요하다. 

각 노드의 경우의 수를 n개로 늘리는 것이다. 원래는 dis[i]에 i번 노드까지 도착하는데의 최소거리를 저장했다면 이제는 dis[i][j]에 i번 노드에 j번 기름 비용으로 도착하는데 최소거리를 저장하고 있으면 된다. 이러면 기존 dijk의 n배가 되기 때문에 시간복잡도 $O(N^2lgN)$에 문제를 해결할 수 있다.

 

BOJ 13309 고등부 3번 트리

문제 링크 : https://www.acmicpc.net/problem/13309

문제 태그

HLD, LCA

문제 풀이

경로? 경로에 대한 쿼리를 온라인으로 물어본다. 내 지식내에서는 바로 HLD가 떠오를 수 밖에 없었다. HLD로는 세그먼트 트리처럼 경로 구간의 합,곱,min,max 값들을 구할 수 있다.
따라서 모든 간선에 대해서 가중치를 1로 해놓고, 끊어진 간선은 가중치를 0으로 한 다음에 경로 구간에 대한 가중치의 합이 거리와 일치하면 경로상의 모든 간선이 살아있기 때문에 경로가 존재한다고 할 수 있다. 거리는 lca를 이용하여 구할 수 있다. (문제 정점들의 거리)
HLD에서는 연습문제 급이라서 HLD를 이용해 문제를 푼 나로써는 더이상 딱히 할 말이 없을 것 같다.

...원래 HLD 글을 빨리 올리려고 했는데 늦어졌다. 조만간 하려고 한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back

struct edg{
    ll i,v,g;
};

ll n;
ll par[210101][21];
ll vis[1010101];
ll dep[1010101];
ll sz[1010101];
ll in[1010101];
ll out[1010101];
ll top[1010101];
ll ptn[1010101];
vector<ll> dv[1010101];
vector<edg> v[1010101];
ll dupt[1010101];

void dfs1(ll x){
    sz[x]=1;
    for(auto n:v[x]){
        if(sz[n.g]) continue;
        dep[n.g]=dep[x]+1;
        par[n.g][0]=x;
        ptn[n.i]=n.g;
        dfs1(n.g);
        dupt[n.g]=n.v;
        sz[x]+=sz[n.g];
        dv[x].push_back(n.g);
        if(sz[n.g]>sz[dv[x][0]]) swap(dv[x][0],dv[x].back());
    }
}

ll np;
void dfs2(ll x){
    np++;
    in[x]=np;
    for(auto k:dv[x]){
        if(dv[x][0]==k) top[k]=top[x];
        else top[k]=k;
        dfs2(k);
    }
    out[x]=np;
}

void f(){
    ll i,j;
    for(j=1;j<21;j++)
        for(i=1;i<=n;i++)
            par[i][j]=par[par[i][j-1]][j-1];
}

ll lca(ll x,ll y){
    if(dep[x]>dep[y]) swap(x,y);
    for(int i=20 ;i>=0;i--){
        if(dep[y]-dep[x]>=(1<<i)) y=par[y][i];
    }

    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            x=par[x][i];
            y=par[y][i];
        }
    }
    return par[x][0];
}

ll arr[1010101];
ll tree[5050505];

ll upt(ll idx,ll val,ll s,ll e,ll nod){
    if(idx<s||idx>e) return tree[nod];
    if(s==e) return tree[nod]=val;
    return tree[nod]=upt(idx,val,s,(s+e)/2,nod*2)+upt(idx,val,(s+e)/2+1,e,nod*2+1);
}

ll sol(ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return 0;
    if(l<=s&&e<=r) return tree[nod];
    return sol(l,r,s,(s+e)/2,nod*2)+sol(l,r,(s+e)/2+1,e,nod*2+1);
}

ll psol(ll a,ll b){
    ll ans = 0;
    while(top[a]!=top[b]){
        if(dep[top[a]] > dep[top[b]]) swap(a, b);
        ll x=top[b];
        ans+=sol(in[x],in[b],1,n,1);
        b=par[x][0];
        //printf("%lld %lld %lld\n",a,b,ans);
    }
    if(dep[a]>dep[b]) swap(a, b);
    if(a==b) return ans;
    ans+=sol(in[a]+1,in[b],1,n,1); 
    return ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,a,b,c,d;
    cin>>n>>m;

    for(i=2;i<=n;i++){
        cin>>a;
        ll c=1;
        ll b=i;
        edg e1={i,c,b};
        edg e2={i,c,a};
        v[a].push_back(e1);
        v[b].push_back(e2);
    }

    dfs1(1);
    top[1]=1;
    dfs2(1);
    f();
    for(i=2;i<=n;i++){
        upt(in[i],dupt[i],1,n,1);
    }

    while(m--){
        cin>>a>>b>>c;
        //cout<<psol(a,b)<<' '<<dep[a]<<' '<<dep[b]<<' '<<lca(a,b)<<' '<<dep[lca(a,b)]<<'\n';
        if(c==0){
            if(psol(a,b)==dep[a]+dep[b]-dep[lca(a,b)]*2){
                cout<<"YES"<<'\n';
            }
            else{
                cout<<"NO"<<'\n';
            }
        }
        else{
            if(psol(a,b)==dep[a]+dep[b]-dep[lca(a,b)]*2){
                cout<<"YES"<<'\n';
                upt(in[ptn[a]],0,1,n,1);
            }
            else{
                cout<<"NO"<<'\n';
                upt(in[ptn[b]],0,1,n,1);
            }
        }
    }
}

BOJ 13310 고등부 4번 먼 별

문제 링크 : https://www.acmicpc.net/problem/13310

문제 풀이 링크 : https://stonejjun.tistory.com/138