9도 OJ 1360: 로또 맞히기 게임(귀속)

시간 제한: 2초
메모리 제한: 32메가바이트
특수 판제: 아니요
제출: 955
해결
제목 설명:
어린이날이 되자 YZ는 푸짐한 선물을 사서 JOBDU의 고생한 직원들에게 보상을 준비했다.그는 재미를 더하기 위해 다양한 종류의 주사위를 준비해 주사위를 던져 숫자를 맞히는 방식으로 상품을 지급할 계획이다.예를 들어 어떤 주사위는 6개의 포인트(포인트는 각각 1~6), 어떤 주사위는 7개(포인트는 각각 1~7), 그리고 어떤 주사위는 8개의 포인트(포인트는 각각 1~8)가 있다.그는 매번 n개의 같은 유형의 주사위 (그것들이 모두 m개의 포인트를 가지고 있고 나타날 확률이 같다고 가정) 를 꺼내 던지고 직원들에게 종이에 우선순위 (고에서 저까지) 의 순서에 따라 3개의 수를 써서 건네주어 그들이 이 주사위가 가장 가능성이 있다고 생각하는 점수의 합이 얼마인지 표시했다.첫 번째 숫자를 맞힌 사람은 일등상이다.두 번째 숫자로 맞힌 사람은 2등상이다.만약 세 수가 모두 정답이 아니라면, 낙심하지 마라!YZ는 막대사탕도 많이 준비했어요.ZL은 똑똑해서 확률(두 소수를 보존하는 확률계)이 가장 높은 세 수를 찾아내고 확률이 같으면 그 중에서 포인트와 가장 작은 수를 선택하려고 생각했다.ZL이 세 개씩 쓸 것 같아요?
입력:
여러 그룹의 데이터를 입력합니다.
각 그룹의 데이터 한 줄에는 2개의 정수 n(0<=n<=10), m(6<=m<=8), n은 YZ가 꺼낸 주사위 수를 나타내고, m는 주사위가 가진 포인트를 나타낸다.n=0이면 입력이 종료됩니다.
출력:
각 그룹의 데이터에 대응하여 ZL이 가장 순서대로 쓸 수 있는 점과 그에 대응하는 확률 값을 출력합니다.확률치는 4 반올림 요구에 따라 2위 소수를 보류한다.각 그룹의 데이터 사이에 한 줄이 비어 있습니다. 주의: 마지막 그룹의 데이터 끝에 빈 줄이 없습니다.
샘플 입력:

1 6
4 6
3 7
0

샘플 출력:

1 0.17
2 0.17
3 0.17

13 0.11
14 0.11
15 0.11

12 0.11
10 0.10
11 0.10

생각:
주사위를 여러 번 던져서 얻은 합이 A라는 뜻으로 그 분포에서 가장 높은 확률이 나오는 세 수를 찾아낸다.
과감하게 귀속되거나 동적 기획으로 해결하고 N+1차 이후의 결과는 N차 결과에서 나온다.
코드:

#include <stdio.h>
#include <stdlib.h>
 
#define N 10
#define M 8
 
struct node {
    int index;
    double p;
} c[N*M+1];
 
int cmp(const void *a, const void *b)
{
    struct node *c = (struct node *)a;
    struct node *d = (struct node *)b;
    if (c->p != d->p)
        return (d->p > c->p) ? 1 : -1;
    else
        return c->index - d->index;
}
 
int main(void)
{
    int n, m, i, j, k;
    double a[N*M+1];
    double b[N*M+1];
    int count;
 
    count = 0;
    while (scanf("%d", &n) != EOF && n)
    {
        scanf("%d", &m);
        b[0] = 1;
        for(i=1; i<=n; i++)
        {
            for (j=i; j<=i*m; j++)
            {
                a[j] = 0;
                for (k=j-1; k>=j-m; k--)
                {
                    if (k>=i-1 && k<=(i-1)*m)
                        a[j] += b[k]/m;
                }
                //if (i == n)
                //  printf("%d: %.4lf
", j, a[j]);
            }
            for (j=i; j<=i*m; j++)
                b[j] = a[j];
        }
        for (i=n; i<=n*m; i++)
        {
            c[i-n].index = i;
            double t0 = a[i]*100;
            double t1 = (double)((int)t0);
            double t2 = (double)((int)t0+1);
            double t;
            if (t0-t1 < t2-t0)
                t = t1;
            else
                t = t2;
            c[i-n].p = t/100;
        }
        qsort(c, (m-1)*n+1, sizeof(c[0]), cmp);
        if (count > 0)
            printf("
");
        for (i=0; i<3; i++)
            printf("%d %.2lf
", c[i].index, c[i].p);
        count ++;
    }
 
    return 0;
}
/**************************************************************
    Problem: 1360
    User: liangrx06
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:916 kb
****************************************************************/