4531 - 주사위놀이 (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

에르난데스와 카트리나가 보드게임을 하고 있다.

게임 규칙은 사각형 맵에 말을 올려두고 주사위 n개를 동시에 던져서 나오는 눈의 합만큼 말을 이동시키고, 도시를 건설하여 상대방을 파산시키는 게임이다.

카트리나는 던진 주사위 눈의 합이 S가 나오게 되면 파산한다. 카트리나가 주사위를 던졌을 때 S가 나오게 되는 경우의 수와 확률을 구해보자.

Input

* Line 1 : 주사위의 갯수 n (1 ≤ n ≤ 30)

* Line 2 : 주사위 눈의 합 S ( n ≤ S ≤ 6*n)

Output

* Line 1 : n개의 주사위를 동시에 던질 때, 나오는 눈의 합이 S가 되는 경우의 수를 출력한다.

* Line 2 : n개의 주사위를 동시에 던질 때, 나오는 눈의 합이 S가 될 확률을 기약분수로 출력한다.

* Line 3 : n개의 주사위를 동시에 던질 때, 나오는 눈의 합이 S가 될 확률을 백분율(%)로 소수점 여섯번째 자리에서 버림하여 출력한다.

Sample Input

3
8

Sample Output

21
7/72
9.72222%

Hint

같은 계산을 여러 번 반복하는 것을 매우 비효율적입니다. 한 번 계산한 것을 저장해두면 다시 계산할 필요가 없습니다

 

array[i]에 i번째 피보나치 함수를 저장해두고 재사용하는 코드는 아래와 같습니다.

 

#include <stdio.h>
long long array[100]={0, 1, 1};
long long function(long long n) {
    if (array[n]==0)
        array[n] = function(n-2) + function(n-1); // 이전에 저장한 값이 없으면 새로 계산
    return array[n]; // 저장된 것 불러옴
}
int main() {
    printf("%lld\n", function(80)); // 실행하고나면 array에 피보나치 1~80까지 저장되어있음
    return 0;
}