BOJ 18251 - 내 생각에 A번인 단순 dfs문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

문제 링크 : www.acmicpc.net/problem/18251

문제 풀이

이 문제를 보자마자 연관성이 큰 다른문제가 떠오르게 되었다. 문제 링크는 기억이 안나지만 설명을 하자면, 수열이 주어지고 그 수열에서의 부분 최댓값을 구하는 문제이다. 이 문제는 앞에서 부터 계속 더하면서 최댓값을 관리하고 값이 음수가 되었다면 중간에 계속 0으로 초기화 시키는 것을 반복하는 것으로 $O(N)$에 풀 수 있다. 

다시 이 문제를 살펴보자. 이 문제와 위에서 설명한 문제의 차이점은 높이가 있다는 것이다. 하지만 전체 노드들의 왼쪽에서 부터 오른쪽으로의 순서는 정해져 있다. 그리고 높이는 lgN이다. 
직사각형의 윗변과 아랫변을 정해보자. 이 때 나올 수 있는 경우의 수는 $lg^2N$개이다. 그 두 변 사이에 있는 노드들을 뽑아서 맨 위에 있는 소문제를 풀면 전체 문제를 $O(Nlg^2N)$ 에 해결할 수 있다. 

그러고서 틀렸는데, 주어지는 입력 순서가 높이에 따라서 주어진다. 따라서 주어진 입력을 왼쪽부터 순서대로 바꿔주어야 되는데, 이는 중위순회를 해주는 것으로 해결할 수 있다. 

코드 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
 
pii arr[2010101];
ll st[2010101];
ll nn;
ll cnt;
ll dd;
void dfs(ll x,ll d){
    if(x*2<=nn){
        dfs(x*2,d+1);
    }
    cnt++;
    arr[cnt]={d,st[x]};
    dd=max(dd,d);
    if(x*2+1<=nn){
        dfs(x*2+1,d+1);
    }
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    queue<pii> q;
    for(i=1;i<=n;i++)
        scanf("%lld",&st[i]);
    nn=n;
    dfs(1,1);    
 
 
    ll ans=-1e18;
    for(i=1;i<=dd;i++)
        for(j=i;j<=dd;j++){
            ll val=0;
            for(k=1;k<=n;k++){
                if(arr[k].ff<i||arr[k].ff>j) continue;
                val+=arr[k].ss;
                ans=max(ans,val);
                if(val<0) val=0;
            }
        }
            
 
        printf("%lld",ans);
 
}