백준 1187 숫자 놀이

https://www.acmicpc.net/problem/1187

1187번: 숫자 놀이

$N$이 2의 거듭제곱 꼴이므로 적절히 재귀적인 아이디어를 사용하면 될 것이라는 추측이 가능하다. 풀이는 다음과 같다.

 

1. 전체 수들을 짝수와 홀수로 분류하면 한 쪽은 짝수 개, 한 쪽은 홀수 개 존재할 것이다.

2. 이때 기우성이 같은 수끼리 더해서 새로운 수를 만들면 총 ${{2N-2} \over {2}} = 2 \cdot {{N} \over {2}} -1$개의 짝수를 얻는다. 이들을 2로 나눈 수열을 생각한다.

3. 이제 새로 얻어진 길이 $2 \cdot {N \over 2} -1$의 수열에서 ${N \over 2}$개의 수를 뽑았을 때 ${N \over 2}$의 배수가 되는 수열을 찾으면 된다. 즉 $N$이 절반일 때의 문제 상황과 완전히 같아졌음을 알 수 있다. 재귀함수를 통한 해결이 가능하다.

 

코드는 다음과 같다.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pi;

int n;
int sm[3000][3000];
pi lev[3000][3000];
int u = 2;

void dfs(int a){
    if(a==1) return;
    int prv = -1;
    int t = 0;
    for(int i=0;i<2*a-1;i++){
        if(sm[i][a]%u){
            if(prv==-1) prv = i;
            else{
                sm[t][a/2] = sm[prv][a]+sm[i][a];
                lev[t][a/2] = pi(prv, i);
                ++t;
                prv = -1;
            }
        }
    }
    prv = -1;
    for(int i=0;i<2*a-1;i++){
        if(sm[i][a]%u==0){
            if(prv==-1) prv = i;
            else{
                sm[t][a/2] = sm[prv][a]+sm[i][a];
                lev[t][a/2] = pi(prv, i);
                ++t;
                prv = -1;
            }
        }
    }
    u *= 2;
    dfs(a/2);
}

void prn(int a, int idx){
    if(a==n){
        printf("%d ", sm[idx][a]);
        return;
    }
    prn(a*2, lev[idx][a].first);
    prn(a*2, lev[idx][a].second);
}

int main(){
    scanf("%d", &n);
    for(int i=0;i<2*n-1;i++) scanf("%d", &sm[i][n]);
    dfs(n);
    prn(1, 0);
}