1089 - 엘리베이터

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

2082번: 시계같은 구현문제일 줄 알고 가벼운 마음으로 시작했다.
풀다보니 모든 수의 합을 구하는 과정에서 DP로 작성하고 있었다. (하지만 DP로는 풀지 못했다.)

우선 각 자리에서 나올 수 있는 숫자들을 추려냈고, (이 과정은 2082번 풀이를 참고)
만들어진 수에 이전에 나온 경우의 수만큼 곱한다. 그만큼 중복으로 등장하기 때문이다.

각 자리에서 나올 수 있는 수를 괄호로 묶었을 때, $(0, 8)$, $(8, 9)$ (예제)와 같은 경우는 1의 자리에서 $8, 9$가 두번씩 나온다. 자리수가 길수록, 다른 자리에 가능한 수가 다양할수록 등장 횟수는 많아질 것이다. 그래서 DP를 생각했다.
가능한 숫자들의 합을 구하는 DP 코드는 아래와 같다.

typedef long long lld;

int n;
vector<int> cand[10]; // i번째 자리에 가능한 숫자들
int nCase[11];
lld DEC[11]={1,1,10,100,1e4,1e5,1e6,1e7,1e8,1e9};

lld dp[11];
lld sum(int pos){
    if(pos >= n) return 0;
    
    lld& r = dp[pos];
    if(r != -1) return r;
    
    r = 0;
    for(int i=0; i<cand[pos].size(); ++i){
        r += nCase[pos+1] * cand[pos][i] * DEC[n-pos] + sum(pos+1);
    }
    return r;
}

뭔가 찝찝한 느낌이 있었는데 채점 40% 정도에서 틀렸다. 오버플로우가 아닐까 싶었다.

아래 입력은 각 자리마다 $(2, 8), (0, 2, 8), (3, 8, 9)$ 의 조합으로 수가 만들어질 수 있다.

3
###.###.###
..#...#...#
.#......##.
#...#.....#
###.###....

위 입력의 정답은 $540.0$ 이다.

가능한 수를 모두 적어보면 아래와 같다.

203
208
209
223
228
229
283
288
289
803
808
809
823
828
829
883
888
889

1의 자리에서 (3+8+9)가 6번 나온다. 10의 자리에서 (0+20+80)이 2번*3번 나온다.
이런식으로 수를 쪼개보면 $10^x$의 자리에서 나올 수 있는 수들의 합은 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) 이다.

지금 이걸 하려는 이유가 합을 모두 누적한다면 오버플로우가 나기 때문이라고 생각해서이다.
평균값은 (전체의 합)$/$개수이므로 어떤 수 하나의 비율은 (수 하나)$/$개수 이다. 각 숫자들의 비율을 모두 더해도 평균은 똑같이 구할 수 있다!

비율로 계산한다면 (자리에서 가능한 숫자들의 합) $\ast$ (전체 경우의 수 / 가능한 숫자의 개수) / (전체 경우의 수) 를 누적하면 되는 데 약분하면, (자리에서 가능한 숫자들의 합) / (가능한 숫자의 개수) 이다.

풀고 난 후

long long으로 해도 오버플로우는 안 난다.

lld DEC[11]={1,1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9};

배열에서 1e3를 빼먹어서 틀린거였다..

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

char s[5][40] = {
    "###..########.################",
    "#.#..#..#..##.##..#....##.##.#",
    "#.#..################..#######",
    "#.#..##....#..#..##.#..##.#..#",
    "###..#######..#######..#######"
};

char e[40][40];

bool maybeOk(int x, int num){
    for(int i=0; i<5; ++i){
        for(int j=x; j<x+3; ++j){
            if(e[i][j]=='#' && s[i][3*num+(j-x)]=='.') return false;
        }
    }
    return true;
}

int main(){
    int n;
    scanf("%d ", &n);
    for(int i=0; i<5; ++i) scanf("%s ", e[i]);
    int len = 4*n-1;
    vector<int> cand[10];
    for(int i=0; i<len; i+=4){
        for(int k=0; k<10; ++k){
            if(maybeOk(i, k)){
                //printf("%d ", k);
                cand[i/4].push_back(k);
            }
        }
        //puts("");
    }
    
    vector<int> sum(n, 0);
    for(int i=n-1; i>=0; --i){
        int size = cand[i].size();
        if(size < 1) return puts("-1"), 0;
        for(int j=0; j<size; ++j) sum[i] += cand[i][j];
    }
    
    lld DEC[11]={1,1,10,100,1e3,1e4,1e5,1e6,1e7,1e8,1e9};
    double ret = 0;
    for(int i=0; i<n; ++i){
        ret += (DEC[n-i]*sum[i]+1e-15)/cand[i].size();
    }
    printf("%.10lf", ret);
    
    return 0;
}

/*
각 수를 쪼개면 아래와 같이 나옴

(3+8+9)*(18/3) = 120
(00+20+80)*(18/3) = 600
(200+800)*(18/2) = 9000

비율 = (그룹의 합)*(전체 경우의 수/그룹 원소의 개수)/(전체 경우의 수)

각 비율만큼 누적.
*/