[백준 1089] 스타트링크 타워

작성일 | In |

문제 링크

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

풀이

한 자리가 어떤 숫자가 될 수 있다는 것은 숫자에서 꺼져있는 전구가 자리에서 켜져있지만 않으면 됩니다. 그러므로 어떤 상태가 주어졌을 때 그 자리에 들어갈수 있는 숫자의 후보를 찾아낼 수 있습니다. 당연하게도 후보들의 나올 확률은 모두 동일하기 때문에 그 후보들의 평균을 정답에 더해주기만 하면 됩니다. 후보가 없을 때에는 -1을 출력하는 것을 잊지 말아야 합니다. 전구를 비교하는 것은 상수 시간이기 때문에 시간복잡도는 $O(N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
string s[5], num[10][5] = {
    {"###","#.#","#.#","#.#","###"},
    {"..#","..#","..#","..#","..#"},
    {"###","..#","###","#..","###"},
    {"###","..#","###","..#","###"},
    {"#.#","#.#","###","..#","..#"},
    {"###","#..","###","..#","###"},
    {"###","#..","###","#.#","###"},
    {"###","..#","..#","..#","..#"},
    {"###","#.#","###","#.#","###"},
    {"###","#.#","###","..#","###"}
};

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i=0;i<5;i++) cin >> s[i];

    double ans = 0, g = 1;
    for(int i=n-1;i>=0;i--){
        int c = 0, cnt = 0;
        for(int j=0;j<10;j++){
            int flag = 1;
            for(int k=0;k<5;k++) for(int l=0;l<3;l++) if(num[j][k][l] == '.' && s[k][4*i+l] == '#') flag = 0;
            if(flag) cnt++, c += j;
        }
        if(cnt == 0) return cout << -1, 0;
        ans += g * c / cnt, g *= 10;
    }
    cout << ans;
}

여담

저는 개인적으로 실버 4정도라고 생각하지만 다른분들 의견 따라 실버 2로 투표했습니다.