POJ 3628 - Bookshelf 2

DFS
 
 
제목은 대체로 다음과 같다. 즉, FJ는 난간이 있고 난간에 높이가 H가 있다. 현재 FJ에는 N개의 젖소가 있는데 각 젖소마다 높이가 있다. 지금은 젖소를 쌓아 올리고 (여기는 어떻게 번역했는지 모르겠다) 쌓아 올리는 높이가 H보다 크다. 지금은 최소 높이의 차이를 요구한다.
 
이전에 저는 dp로 하려고 했는데 제출해도 계속 WA를 했습니다. 오류 코드는 다음과 같습니다.

#include <stdio.h>
#include <string.h>
int main()
{
    int i,j;
    int n,b,h[25],sum,dp[20000005];
    while(scanf("%d%d",&n,&b));
    {
        sum=0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&h[i]);
            sum+=h[i];
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(i=0; i<n; i++)
            for(j=sum; j>=h[i]; --j)
                {
                    if(dp[j-h[i]])
                        dp[j]=1;
                }
        for(i=b; i<=sum; i++)
            {
                if(dp[i])
                {
                    printf("%d
",i-b);
                    break;
                }
            }
    }
    return 0;
}

나중에 인터넷에서 많은 사람들이 DFS로 쓰는 것을 보고 AC가 되었다.
 
DFS 코드에서 최적화된 기능은 다음과 같습니다.
1. 우선 검색 순서로 큰 것부터 작은 것까지 배열이 뛰어나오기 좋다.
2.현재 높이+최소 높이-H>=min(현재 최소 높이)일 때 점프합니다.
3. 최소 고도차 min을 요구하기 때문에 0이 될 때 바로 튀어나옵니다.
AC 코드는 다음과 같습니다.

#include <stdio.h>
#define M 1000005
int N,H;
int h[M],min,sum = 0;
void init()
{
    int i,j,tmp;
    scanf("%d%d",&N,&H);
    for (i=0;i < N; i++)
    {
        scanf("%d",&h[i]);
        sum+=h[i];
    }
    for (i=0;i < N-1;i++)
        for (j=i+1;j<N;j++)
        if (h[i]<h[j])
        {
            tmp = h[i];
            h[i] = h[j];
            h[j] = tmp;
        }
    min = sum-H;
}
void DFS(int depth , int sum)
{
    if (!min) return;
    if (sum >= H)
    {
        if(sum - H < min)
            min = sum - H;
    }
    if (depth == N) return ;
    if (sum + h[N-1] - H >= min) return ;
    DFS(depth + 1,sum + h[depth]);
    DFS(depth + 1,sum);
}

int main()
{
    init();
    DFS(0,0);
    printf("%d
",min);
    return 0;
}