문제를 열심히 풀었는데 계속 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;
}


						

						14년 전