스타트링크 타워( BOJ 1089 )

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

1089번: 스타트링크 타워

 

문제 파악하기

엘리베이터의 전구를 파악해서 나올 수 있는 모든 숫자의 평균을 구하는 문제입니다. 10^-5까지의 오차를 허용하기 때문에 맨 마지막에 평균을 구해주면 실수 값을 처리하는데 크게 문제가 없는 문제입니다. 이 문제에서 조금 까다로운 부분은 엘리베이터의 층을 표현하는 부분입니다. 층과 층 사이는 '.'으로 구분되어 있으며, 숫자들은 0부터 9까지 서로 다른 모습을 가지고 있습니다. 또한, 엘리베이터의 전구 중 몇 개는 고장나서 원래는 켜져있지만( # ) 꺼진 것처럼( . ) 보일 수도 있다고 합니다. 그렇기에 확실하게 현재 보이는 전구 모습을 토대로 될 수 있는 숫자를 카운트하기 위해서는 입력된 값을 비교하기 편하게 바꾸는 작업이 필요합니다.

 

만약 나올 수 있는 숫자를 모두 구했다면 남은 작업은 바로 만들 수 있는 모든 숫자의 평균을 구하는 것입니다. 모든 숫자의 평균을 구하는 가장 간단한 방법은 나올 수 있는 모든 숫자를 구하는 것이지만, 아쉽게도 최악의 경우를 생각해보면 10⁹가지 경우의 수가 나옵니다. 이 정도 가짓수를 구하기에 1초는 턱없이 부족합니다. 따라서, 우리는 좀 더 효율적인 알고리즘인 숫자를 분해해서 합을 구한 다음, 평균을 구하는 방법을 사용해야 합니다. 이렇게 평균을 구하면 문제를 제한시간 안에 해결할 수 있습니다.

 

문제 해결하기

우선, 입력된 값이 될 수 있는 숫자를 구하기 위한 사전작업을 진행해봅시다. 어떤 입력값이 특정 숫자가 되기 위해서는 사실 한 가지 조건만 만족하면 됩니다. 입력값의 전구 중에서 확인할 숫자의 전구가 꺼져있는 위치에 전구가 켜져있지만 않으면 됩니다. 이 조건만 만족한다면 입력값은 해당 숫자가 될 수 있습니다. 그럼 어떻게 하면 효율적으로 숫자와 입력값을 비교할 수 있을까요? 바로 비교할 모든 값을 1차원 배열로 변환하면 됩니다. 0부터 9까지의 숫자를 모두 1차원 배열의 값으로 저장한 다음, 입력된 값을 적절하게 파싱하여 자릿수마다 1차원 배열에 저장하면 손쉽게 비교할 수 있습니다.

 

이렇게 나올 수 있는 숫자를 파악했다면 나온 숫자들을 가지고 경우의 수를 구하면 됩니다. 여기서 중요한 점은 평균을 구할 때, 꼭 완성된 숫자가 필요하지 않다는 점입니다. 각각의 자릿수에서 나온 숫자들을 사용될 횟수만큼 총합에 더해주면 됩니다. 예를 들어, 예제 입력2를 보면 일의 자리에 (8, 9)가 들어갈 수 있습니다. 그렇다는 건 십의 자리에 어떤 숫자가 오든지 항상 일의 자리는 8 또는 9라는 뜻이며, 총 합을 구할 때에는 (8, 9)에 일의 자리 앞에 숫자들이 될 수 있는 모든 경우만큼 곱해서 총 합에 더해주면 됩니다. 마찬가지로 십의 자리에는 (0, 8)이 들어갈 수 있으며, 이 숫자들 역시 일의 자리 숫자들이 될 수 있는 모든 경우만큼 곱해서 총 합에 더해주면 됩니다. 이렇게 자릿수마다 따로 합을 구한 다음에, 나올 수 있는 모든 숫자의 경우의 수만큼 나눠주면 정답을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#define lint long long int
using namespace std;
 
/*
###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###
*/
int N;
char str[5][40], light[10][20];;
char check[10][20] = {
        "####.##.##.####", "..#..#..#..#..#", "###..#####..###", "###..####..####",
        "#.##.####..#..#", "####..###..####", "####..####.####", "###..#..#..#..#",
        "####.#####.####", "####.####..####"
};
 
int f;
lint cnt, digit, ret;
vector< int > num[10];
 
bool isPossible(int lightIdx, int checkIdx) {
    for(int j=0;j<15;j++) {
        if(light[lightIdx][j] == '#' and check[checkIdx][j] == '.') return 0;
    }
 
    return 1;
}
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<5;i++) scanf("%s", str[i]);
 
    for(int i=0;i<5;i++) {
        for(int j=0;j<4*N;j++) {
            if(j%4 == 3) continue;
 
            light[j/4][3*i+j%4] = str[i][j];
        }
    }
 
    f = 1;
    for(int i=0;i<N and f;i++) {
        for(int j=0;j<10;j++) {
            if(isPossible(i, j)) num[(N-1)-i].push_back(j);
        }
 
        if(num[(N-1)-i].empty()) f = 0;
    }
 
    if(f == 0) printf("-1");
    else {
        // 모든 숫자의 합 구하기(자릿수마다 따로 더하기)
        digit = 1;
        for(int i=0;i<N;i++) {
            cnt = 1;
            for(int j=0;j<N;j++) {
                if(i == j) continue;
                cnt *= (int)num[j].size();
            }
 
            for(int cur:num[i]) ret += cur*digit*cnt;
 
            digit *= 10;
        }
 
        // 전체 경우의 수 구하기
        cnt = 1;
        for(int i=0;i<N;i++) cnt *= num[i].size();
 
        printf("%lf", (double)ret/cnt);
    }
}

후기

2차원 배열을 1차원 배열로 바꾸는 작업이 귀찮았지만, 평균을 자릿수마다 따로 구하는 방법이 재미있던 문제입니다. 구현에 난이도가 조금 있지만 알고리즘을 배우는 초보자에게 소개할만한 문제라고 생각합니다.