BOJ 1089 - 스타트링크 타워 링크
(2023.05.04 기준 G4)

문제

다음과 같이 전구가 숫자를 나타낸다.

그런데 일부는 고장이 나서 항상 꺼져있는 상태이다. 이 때, 현재 번호판이 나타낼 수 있는 모든 번호의 평균 출력

알고리즘

빡구현 and 확률론을 가미한 약간의 수학

풀이

전구는 고장이 나서 꺼질 수 있지만, 꺼져 있던 것이 켜질 수는 없다.
그러므로 켜져있는 전구의 자리마다 불가능한 수들을 걸러내 가능한 숫자의 목록을 만들면 된다. 이는 그냥 빡구현하면 된다. ^^

그런데 문제가 있다.
가능한 모든 수를 전부 더해 경우의 수로 나누는 방식은 TLE 혹은 MLE가 날 것이다.

그러므로 자리마다 가능한 경우의 수의 평균을 합해주는 방식을 택하자.

위와 같이 증명이 가능하다.

코드

• C++

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

// 빠른 거듭제곱
int fpow(int x, int n){
    int result = 1;
    while (n){
        if (n & 1) result = result * x;
        x = x * x;
        n >>= 1;
    }
    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N; string matrix[5];
    cin >> N;
    for (int i = 0; i < 5; i++) cin >> matrix[i];

    set<int> possible[N]; // 자리별로 가능한 수들
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 10; j++) possible[i].insert(j);

        /**
        OXX XOX
        XXX XXX
        XXX XXX
        XXX XXX
        XXX XXX
        **/
        if (matrix[0][i * 4] == '#')
            possible[i].erase(1);
        if (matrix[0][i * 4 + 1] == '#')
            possible[i].erase(1),
            possible[i].erase(4);
    
        /**
        XXX XXX XXX
        OXX XOX XXO
        XXX XXX XXX
        XXX XXX XXX
        XXX XXX XXX
        **/
        if (matrix[1][i * 4] == '#')
            possible[i].erase(1),
            possible[i].erase(2),
            possible[i].erase(3),
            possible[i].erase(7);
        if (matrix[1][i * 4 + 1] == '#'){
            cout << -1;
            return 0;
        }
        if (matrix[1][i * 4 + 2] == '#')
            possible[i].erase(5),
            possible[i].erase(6);
    
        /**
        XXX XXX
        XXX XXX
        OXX XOX
        XXX XXX
        XXX XXX
        **/
        if (matrix[2][i * 4] == '#')
            possible[i].erase(1),
            possible[i].erase(7);
        if (matrix[2][i * 4 + 1] == '#')
            possible[i].erase(0),
            possible[i].erase(1),
            possible[i].erase(7);
    
        /**
        XXX XXX XXX
        XXX XXX XXX
        XXX XXX XXX
        OXX XOX XXO
        XXX XXX XXX
        **/
        if (matrix[3][i * 4] == '#')
            possible[i].erase(1),
            possible[i].erase(3),
            possible[i].erase(4),
            possible[i].erase(5),
            possible[i].erase(7),
            possible[i].erase(9);
        if (matrix[3][i * 4 + 1] == '#'){
            cout << -1;
            return 0;
        }
        if (matrix[3][i * 4 + 2] == '#')
            possible[i].erase(2);
    
        /**
        XXX XXX
        XXX XXX
        XXX XXX
        XXX XXX
        OXX XOX
        **/
        if (matrix[4][i * 4] == '#')
            possible[i].erase(1),
            possible[i].erase(4),
            possible[i].erase(7);
        if (matrix[4][i * 4 + 1] == '#')
            possible[i].erase(1),
            possible[i].erase(4),
            possible[i].erase(7);

        // 가능한 수가 없다면 -1 출력
        if (possible[i].empty()){
            cout << -1;
            return 0;
        }
    }

    // 자리마다 평균을 내서 합하자.
    double result = 0;
    for (int i = 0, sum; i < N; i++){
        sum = 0;
        for (int n: possible[i]) sum += n;
        result += (double)sum / possible[i].size() * fpow(10, N - i - 1);
    }
    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
matrix = [input().strip() for _ in range(5)]

possible = [set(i for i in range(10)) for _ in range(N)] # 자리별로 가능한 수들
for i in range(N):
    impossible = set()

    '''
    OXX XOX
    XXX XXX
    XXX XXX
    XXX XXX
    XXX XXX
    '''
    if matrix[0][i * 4] == '#':
        impossible.add(1)
    if matrix[0][i * 4 + 1] == '#':
        impossible.add(1)
        impossible.add(4)

    '''
    XXX XXX XXX
    OXX XOX XXO
    XXX XXX XXX
    XXX XXX XXX
    XXX XXX XXX
    '''
    if matrix[1][i * 4] == '#':
        impossible.add(1)
        impossible.add(2)
        impossible.add(3)
        impossible.add(7)
    if matrix[1][i * 4 + 1] == '#':
        print(-1)
        exit()
    if matrix[1][i * 4 + 2] == '#':
        impossible.add(5)
        impossible.add(6)

    '''
    XXX XXX
    XXX XXX
    OXX XOX
    XXX XXX
    XXX XXX
    '''
    if matrix[2][i * 4] == '#':
        impossible.add(1)
        impossible.add(7)
    if matrix[2][i * 4 + 1] == '#':
        impossible.add(0)
        impossible.add(1)
        impossible.add(7)

    '''
    XXX XXX XXX
    XXX XXX XXX
    XXX XXX XXX
    OXX XOX XXO
    XXX XXX XXX
    '''
    if matrix[3][i * 4] == '#':
        impossible.add(1)
        impossible.add(3)
        impossible.add(4)
        impossible.add(5)
        impossible.add(7)
        impossible.add(9)
    if matrix[3][i * 4 + 1] == '#':
        print(-1)
        exit()
    if matrix[3][i * 4 + 2] == '#':
        impossible.add(2)

    '''
    XXX XXX
    XXX XXX
    XXX XXX
    XXX XXX
    OXX XOX
    '''
    if matrix[4][i * 4] == '#':
        impossible.add(1)
        impossible.add(4)
        impossible.add(7)
    if matrix[4][i * 4 + 1] == '#':
        impossible.add(1)
        impossible.add(4)
        impossible.add(7)

    possible[i] -= impossible
    if not possible[i]: # 가능한 수가 없다면 -1 출력
        print(-1)
        exit()

# 자리마다 평균을 내서 합하자.
print(sum(sum(possible[i]) / len(possible[i]) * 10 ** (N - i - 1) for i in range(N)))