algospot.com

문제를 열심히 풀었는데 계속 WA가 나와서 질문드립니다.

문제를 요약하자면 M개의 설치 지점에(0~240 인 실수 구간에서)
N개의 카메라를 설치하는데, 설치한 카메라들의 가장 가까운 거리가
최대가 되게 하는 문제입니다.

제가 생각한 해법은, M개의 지점 중 마지막 지점을 고려했을때
문제의 답은
1) M번째 지점에 카메라를 설치하고, M-1번까지 N-1개의 카메라를 설치하거나
2) M번째 지점에 카메라를 설치하지 않고, M-1번까지 N개의 카메라를 설치하거나

둘 중 하나라고 가정합니다. 그런데, 1)번 케이스의 경우 M-1까지의 부분 문제의
최적해가 N번째의 카메라 위치와 N-1번째의 카메라 위치를 고려하지 않은 최적해
이기 때문에 잘못된 답을 택하는 경우가 생기더군요.

그래서 다시 부분구조를 바꿔서
1) M번째 지점에 카메라를 설치하고, M-1번까지 N-1개의 카메라를 설치 이중 최소값
M-2번까지 N-1개의 카메라를 설치 이중 최소값
.....
각각의 경우 중 최대값
2) M번째 지점에 카메라를 설치하지 않고, M-1번까지 N개의 카메라를 설치

1)번과 2)번중 더 큰 값을 답으로 정함

이렇게 부분구조를 바꾸었습니다. 이렇게 되면 고려할 경우의 수가 많아서 수행시간은
길어지지만, 정확한 답을 이끌어 낸다고 생각했습니다.


재귀적으로 따라갈 경우 여러 케이스가 나오는데, S[M][N]를 부분구조의 답이라 했을때,
S[M][N] 에 이미 답이 존재하는 경우
S[M][N]를 리턴합니다.
M == N인 경우
모든 지점에 카메라를 설치하고 그중 가장 작은 값이 S[M][N]의 답입니다.
M < N 인 경우
이 경우는 답이 존재하지 않습니다. 따라서 음수를 S[M][N]에 저장합니다.
N == 2인 경우
왼쪽 가장 끝값(0) 과 오른쪽 가장 끝값을 뺀 값을 S[M][N]에 저장합니다.
M > N 인 경우
위의 부분구조에 의해서 재귀적으로 답을 찾아나갑니다.


위의 방법대로 하면 예제에서는 정확하게 동작합니다. 그런데 제출을 해보면 계속
WA가 나옵니다 ㅠㅠ... 제가 뭔가 잘못 생각한 점이 있는지요? 아니면 단순한 코딩
실수인건가요? 흑

아래는 소스입니다.

* 좀더 예쁘게 글이 보이게 하기 위해 구문 강조를 해놓았습니다(운영자 LIBe)
* 좀더 예쁘게 글이 보이게 하기 위해 다시 수정하였습니다.(본인)

Created with colorer-take5 library. Type 'cpp'



#pragma warning (disable:4996)



#include <stdio.h>

#include <stdlib.h>

#include <queue>

#include <string.h>

using namespace std;



#define MAX           201

#define INF           10000



double C[MAX];                // 문제에서 주어진 입력

double P[MAX][MAX];            // M개�� 설��요소에 N개�� 카메라를 설����는 답

int D[MAX][MAX];            // M개�� 설��요소에 N개�� 카메라를 설��할때 가장 ��른쪽 카메라 인덱스



///////////////////////////////////////////////////////////////

//      입력 제어

///////////////////////////////////////////////////////////////



int GetNumCase()

{

    int _T;

    

    scanf("%d", &_T);



    return _T;

}



void GetNumNM(int *N, int *M)

{

    scanf("%d %d\n", N, M);

    

    return;

}



void InitArray(int M)

{

    int i;



    for (i=0; i<M; i++)

        scanf("%lf", &C[i]);



    return;

}





///////////////////////////////////////////////////////////////

//      알고리��

///////////////////////////////////////////////////////////////



double S(int M, int right)

{

    return C[M] - C[right];

}



double Min(double a, double b)

{

    if (a < b)

        return a;

    else

        return b;

}



double Division(int M, int N)

{

    double max, max2, min, temp, temp2;

    int index1, index2;



    if (P[M][N] > 0.0)

        return P[M][N];



    if (N == 2) {

        P[M][N] = C[M-1] - C[0];

        D[M][N] = M-1;

        return P[M][N];

    }



    if (M == N) {

        min = INF;

        for (int i=1; i<M; i++) {

            temp = C[i] - C[i-1];



            if (min > temp)

                min = temp;

        }

        P[M][N] = min;

        D[M][N] = M-1;

        return P[M][N];

    }



    if (M < N) {

        P[M][N] = -1.0;

        D[M][N] = 0;

        return P[M][N];

    }



    max = Division(M-1, N);

    index1 = D[M-1][N];



    max2 = 0;

    for (int i=1; i<=M-N+1; i++) {

        temp = Division(M-i, N-1);

        temp2 = C[M-1] - C[M-i-1];

        temp = Min(temp, temp2);



        if (max2 < temp) {

            max2 = temp;

            index2 = M-1;

        }

    }    



    if (max > max2) {

        P[M][N] = max;

        D[M][N] = index1;

        return P[M][N];

    }

    else {

        P[M][N] = max2;

        D[M][N] = index2;

        return P[M][N];

    }    

}



///////////////////////////////////////////////////////////////

//        메인 함��

///////////////////////////////////////////////////////////////



int main()

{

    int T, N, M, i;

    double cost;



    T = GetNumCase();

        

    for (i=0; i<T; i++) { 

        GetNumNM(&N, &M);

        InitArray(M);



        for (int m=0; m<M; m++) {

            for (int t=0; t<M; t++) {

                P[m][t] = -1.0;

                D[m][t] = -1;

            }

        }



        cost = Division(M, N);

        printf("%.2lf\n", cost);

    }



    return 0;

}