백준 19847: 여우 신탁

https://www.acmicpc.net/problem/19847

19847번: 여우 신탁

예를 들어 일단 첫 여우는 9개의 수 중 하나를 달라고 할 것이다. 그러면 9개의 숫자들이 나올 확률은 전부 같다. 즉, 각 숫자가 뽑히는 경우의 수를 저장한 배열은

int p[]={1,1,1,1,1,1,1,1,1};

로 나타낼 수 있다.

STEP 0.

입력 두 번째 줄에 받는 숫자들이 예를 들어 9 4 2 라면 여우신은 4 이상 수들은 전부 4로 나눈 나머지를 계산해야 하고, 또 그 후 2 이상 수들은 전부 2로 나눈 나머지를 계산해야 한다.
하지만 예를들어 10 3 5라면 여우신은 3번째 숫자를 부를 땐 굳이 5로 나눈 나머지를 계산하지 않아도 된다. 그 전에 나온 수들이 무조건 3 미만이기 때문에 5로 나눈 나머지는 그 수 그대로이기 때문이다.

그러므로 우리는 두 번째 줄을 입력받을 때 감소하는 수열만 취하고 나머지는 버리면 된다.
ex) 9 4 2 -> 9 4 2 전부 취함
10 3 5 -> 10 3만 가져가고 5는 버림
11 9 15 3 1 -> 11 9 3 1만 가져가고 15는 버림

STEP 1.

9 4 2를 예로 들어 설명하겠다.
'9' 란 0~8까지 각 숫자가 뽑히는 경우의 수가 1임을 뜻한다.


'8'이란 0~7까지 각 숫자가 뽑히는 경우의 수가 1임을 뜻한다.
'n'이란 0~n-1까지 각 숫자가 뽑히는 경우의 수가 1임을 뜻한다.

'9'+'8'란 0~8까지 각 숫자가 뽑히는 경우의 수가 1이고, 거기에 추가로 0~7까지 각 숫자가 뽑히는 경우의 수에 1을 추가한다는 뜻이다.
즉, 0~7까지 각 숫자가 뽑히는 경우의 수는 2이고, 8이 뽑히는 경우의 수는 1이다.

처음에 9개의 수 중 하나를 뽑고 시작했으니 전체 경우의 수는 9이다.
이 때 상황은 '9'로 나타낼 수 있다.

그 다음, 여우신은 4로 나눈 나머지를 구한다.
0~8을
0 1 2 3 / 4 5 6 7 / 8
이렇게 구간으로 나눠보자.

0 1 2 3 은 4로 나누면 그대로 1 2 3 4이다.
4 5 6 7 은 4로 나누면 1 2 3 4가 된다.
8은 4로 나누면 0이 된다.

즉, '9'는 4로 나눈 나머지를 구하는 과정에서 '4'+'4'+'1'이 된다.
(바꾸기 전 '9' 개수)*(9를 4로 나눈 몫)=(바꾼 후 '4' 개수) 이다.
1 * 2 = 1
(바꾸기 전 '9' 개수) = (바꾼 후 '9를 4로 나눈 나머지' 개수) 이다.
(바꾸기 전 '9' 개수) = (바꾼 후 '1' 개수)
1 = 1


그 다음, 여우신은 2로 나눈 나머지를 구한다.
비슷한 과정을 거치면 '4'+'4'+'1' 은 '2'+'2' + '2'+'2' + '1'이 된다.

(바꾸기 전 '4' 개수)*(4를 2로 나눈 몫)=(바꾼 후 '2' 개수) 이다.
2 * 2 = 4
(바꾸기 전 '4' 개수) = (바꾼 후 '4를 2로 나눈 나머지' 개수) 이다.
(바꾸기 전 '4' 개수) = (바꾼 후 '0' 개수)
하지만 '0'의 개수를 따지는 것은 의미가 없으니 생략하자.



'i'의 개수를 dp[i]라고 하자.
아까 예시에선 dp[2]=4, dp[1]=1인 것이다.

처음 상태는 dp[9]=1으로 시작한다.

for(int i=9;i>=0;i--) 을 통해
9에서 시작해서 0으로 1씩 감소하는 i를 설정하자.
일단 9를 4로 나눈다. 그럼 몫은 2이고 나머지는 1이다.
나머지가 1이기 때문에 dp[1]에 dp[9]만큼 증가시킨다.
몫이 2이기 때문에 dp[4]에 2*dp[9]만큼 증가시킨다.
dp[8]~dp[5]는 전부 0이기 때문에 생략하고...

i가 점점 감소해 4에 도달했다.
그럼 이제부터는 여우신은 4가 아니라 2로 나누면 된다.
현재 상태는 dp[4]=2, dp[1]=1이고 그 외에는 전부 0이다.
4를 2로 나눈 몫은 2이고 나머지는 0이다.

그러므로 dp[0]에 dp[4]만큼 증가시킨다 ( 실제로 dp[0]값은 의미 없기때문에 생략 가능 )
몫이 2이기 때문에 dp[2]에 2*dp[4]만큼 증가시킨다.

STEP 2.

'2'+'2'+'2'+'2'+'1'같은 상태는
dp[1]=1, dp[2]=4처럼 저장된다.
우리는 평균을 구할 거기 때문에
sum=0으로 시작해서
각 i에 대해 i*(i-1)/2를 dp[i]번 sum에다 더해주면 된다.

그 후, sum을 전체 경우의 수, 즉 9로 나누면 된다. (맨 처음에 0~8 총 9개 수 중 하나를 뽑았으니)

여우신이 마지막 수를 뽑을 때 2로 나눈 나머지를 구했으므로 i=2까지만 계산해주자. dp[3]부터는 쓸데없는 값들이 저장되어 있다.

다음은 C++로 구현한 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> v;
    int b = 10000005;
    //STEP 0
    for (int p = 0;p < n;p++)
    {
        int h;
        scanf("%d", &h);
        if (h < b)
        {
            v.push_back(h);
            b = h; // 3시간동안 삽질한 이유
        }
    }
    int g = v.front();
    int dp[1000006] = { 0 };
    //STEP 1
    dp[g] = 1;
    int ind = 0;
    for (int i = g;i >= 0;i--)
    {
        int j = v[ind];
        if (i <= j)
        {
            ind++;
            if (ind == v.size())
                break;
        }
        j = v[ind];
        dp[i % j] += dp[i];
        dp[j] += (i / j) * dp[i];
    }
    ind--;
    //STEP 2
    ll sum = 0;
    ll ggg = g;
    for (ll i = 0;i < v[ind] + 1;i++)
    {
        ll ti = i * (i - 1) / 2;
        ll ddd = dp[i];
        sum += ddd * ti;
    }
    ll div = sum / ggg;
    printf("%lld.", div);
    ll c = sum;
    for (ll i = 0;i < 13;i++) // 13은 소수점 아래 13번째 자리까지 출력하고 싶다는 의미
    {
        c = c % ggg;
        c *= 10;
        printf("%d", c / ggg);
    }
}

사실 dp[] 배열에 단순히 dp[i]에 i가 뽑히는 경우의 수를 저장하고 풀어도 답이 나온다. 하지만 내 풀이를 소개하고 싶어 이렇게 썼다. 무려 3시간동안 무려 틀렸습니다 14개를 받으며 겨우 풀었는데 허무하게도 사실 틀린 이유는 바로 20번째 줄의 b=h;를 if문 바깥에 놓아서 그런 거였다.

dp[] 배열에 단순히 dp[i]에 i가 뽑히는 경우의 수를 저장하는 풀이는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include<vector>
 
using namespace std;
typedef long long ll;
 
 
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> v;
    int b = 10000005;
    for (int p = 0;p < n;p++)
    {
        int h;
        scanf("%d", &h);
        if (h < b)
        {
            b = h;
            v.push_back(h);
        }
 
    }
    int g = v.front();
 
    int dp[1000006] = { 0 };
 
    for (int i = 0;i < g;i++)
    {
        dp[i] = 1;
    }
    int ind = 1;
    for (int i = g - 1;i >= 0;i--)
    {
        if (ind >= v.size())
            break;
        if (v[ind] > i)
            ind++;
        if (ind >= v.size())
            break;
        dp[i % v[ind]] += dp[i];
    }
    ind--;
    ll sum = 0;
    ll div = 0;
    ll ggg = g;
    for (ll i = 0;i < v[ind];i++)
    {
        ll ddd = dp[i];
        sum += i * ddd;
    }
    div = sum / ggg;
    printf("%lld.", div);
    ll c = sum;
    for (ll i = 0;i < 13;i++)
    {
        c = c % ggg;
        c *= 10;
        printf("%d", c / ggg);
    }
}