2082번: 시계같은 구현문제일 줄 알고 가벼운 마음으로 시작했다.
풀다보니 모든 수의 합을 구하는 과정에서 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
비율 = (그룹의 합)*(전체 경우의 수/그룹 원소의 개수)/(전체 경우의 수)
각 비율만큼 누적.
*/
댓글 없음:
댓글 쓰기