🔍 1089 스타트링크 타워

스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다.

숫자 1개를 표현하려면 전구 5×3개가 필요하고, 이 전구를 세로 크기 5, 가로 크기 3인 격자 형태로 배치한다. 다음은 0부터 9까지 숫자를 나타낸 것이다. '#'는 불이 켜져있는 전구, '.'는 불이 꺼져있는 전구이다.

###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###

엘리베이터에 있는 층 번호 안내판의 상태가 주어진다. 안내판의 각 숫자는 불이 꺼져있는 전구 한 열로 구분되어 있다. 안내판의 일부 전구는 고장이 나서 항상 꺼져있는 상태이다. 꺼져있는 전구의 일부가 고장이 났다고 가정할 때, 현재 층 번호 안내판이 나타내고 있다고 볼 수 있는 모든 층 번호의 평균을 구해보자.

---

🤔 풀이

1. 처음 풀이

vector<vector<int> > number_shape = { {0, 1, 1, 1, 0}, // 0
                            {2, 2, 2, 2, 2}, // 1
                            {0, 2, 0, 3, 0}, // 2
                            {0, 2, 0, 2, 0}, // 3
                            {1, 1, 0, 2, 2}, // 4
                            {0, 3, 0, 2, 0}, // 5
                            {0, 3, 0, 1, 0}, // 6
                            {0, 2, 2, 2, 2}, // 7
                            {0, 1, 0, 1, 0}, // 8
                            {0, 1, 0, 2, 0} }; // 9 // int[10][5]

vector<vector<char> > shape = {{'#', '#', '#'}, {'#', '.', '#'}, {'.', '.', '#'}, {'#', '.', '.'}}; // char[4][3]

• 전광판의 숫자를 표시하는 한 라인을 다음과 같은 모양으로 나눌 수 있다. number_shape[1]이라면, 숫자 1을 표현하기 위해 필요한 라인의 모양을 나타내는 것이다.
• 처음 전광판 상태를 입력받을 때, 켜지지 않은 전등의 위치를 저장하는 space 벡터에 push한다. 이 전등들을 하나씩 끄고 키면서 해당 칸이 어떤 숫자를 나타내는지 확인하고 그 칸에 해당 숫자가 가능하다는 것을 업데이트해준다.

여기서 문제점이 두 가지 있었다.
1. 두 숫자 사이에 있는 꺼진 전등까지 space에 포함했다.
2. 전등을 하나씩 껐다키며 백트래킹으로 진행하면 시간초과가 일어난다.
+설상가상 outofbound까지, 어디서 일어난건지 아직 모르겠다...

2. 최종

따라서 구현방법을 바꾸어 보았다. 숫자를 표시하기 위해서는 어차피 특정 라인모양만 사용한다. 따라서 현재 전광판의 상태에서, 하나의 숫자칸(5x3)에 있는 어떤 라인을 살펴보자. 그 라인의 꺼진 전등을 켜서 만들 수 있는 경우의 수는 정해져있다. (eg. 라인의 세 전등이 모두 꺼져있다면 전등을 켜서 만들 수 있는 경우의 수는 2^3) 만약 숫자를 표시하기 위해서 사용되는 라인까지 포함하면 경우를 더 좁힐 수 있다.

(.#.와 .##, ##. 은 어차피 숫자에 사용되지 않는다.)

idx	->line	전등을 켜서 만들 수 있는 모양	->idx
0	...	... | ..# | #.. | #.# | ###	0 1 4 5 7
1	..#	..# | #.# | ###	1 5 7
2	.#.	###	7
3	.##	###	7
4	#..	#.. | #.# | ###	4 5 7
5	#.#	#.# | ###	5 7
6	##.	###	7
7	###	###	7

위 라인 모양을 따라 숫자를 표시하면 다음과 같다.

0 {7, 5, 5, 5, 7}
1 {1, 1, 1, 1, 1}
2 {7, 1, 7, 4, 7}
3 {7, 1, 7, 1, 7}
4 {5, 5, 7, 1, 1}
5 {7, 4, 7, 1, 7}
6 {7, 4, 7, 5, 7}
7 {7, 1, 1, 1, 1}
8 {7, 5, 7, 5, 7}
9 {7, 5, 7, 1, 7}

• 따라서 전광판의 숫자칸의 현재 라인모양을 나열하고, 해당 라인들의 전등을 켜서 어떤 라인을 만들 수 있는지 구하고, 그 결과가 숫자로 나타나는지 구하면 된다.

eg) (possible_num) 숫자칸의 현재 모양이 [5 5 0 5 5] 일 때, (number_scan) 라인1은 5이므로 5, 7이 될수있고, 같은 숫자를 가진 라인2, 4, 5도 마찬가지이다. 라인3은 0이므로 0, 1, 4, 5, 7 라인 모양이 될 수 있다. 해당 가능성을 가지고 백트래킹으로 탐색한다. (number_check) 라인5까지 탐색을 마치면 해당 모양이 어떤 숫자를 나타내는지 확인한다. 만약 숫자를 나타낸다면, 그 숫자칸이 될 수 있는 숫자로 경우의 수를 추가한다. (여기서 다른 백트래킹 경로로 해당 숫자가 나타날 수 있으므로, 해당 숫자가 이전에 나왔는지 판단하는 pos_have[9][10] 사용)

• N개의 숫자칸에 나올 수 있는 숫자들을 해당 방식으로 구하고, 이제 합계를 구하여 평균을 구할 차례이다.
  <방법0> 가능한 숫자들을 진짜 모두 더한다.
  <방법1> 숫자칸의 자릿수가 정해져 있으므로, 각각 숫자칸에 나오는 숫자들의 합을 구한다. 3개의 숫자칸이 있고 각각의 숫자칸에서 나올 수 있는 숫자의 경우수가 각각 2, 2, 3 이라면 : 총 2x2x3개의 숫자가 가능하다. 그리고 첫번째 숫자칸에 가능한 숫자1은 전체 경우의 수에서 2x3번 나온다. 세번째 숫자칸에서 가능한 숫자1은 전체 경우의 수에서 2x2번 나온다. 따라서 나는 매우 정직하게 저 수식으로 합계를 계산했었다.
  <방법2> 숫자칸의 자릿수가 정해져 있으므로, 각각 숫자칸에 나오는 숫자들의 합을 구한다. 단, 여기서 숫자칸에서 나올 수 있는 숫자들을 더하고 그 개수로 나눈 평균을 자릿수에 맞춰 더하면 평균이 구해진다.

###.###
#.#.#.#
#.#.###
#.#...#
###.###
숫자칸1에서 가능한 숫자 : 0 8 => (0+8)/2 = 4
숫자칸2에서 가능한 숫자 : 8 9 => (8+9)/2 = 8.5
만들 수 있는 숫자 : 08 09 88 89 => (8+9+88+89)/4 = 48.5
<방법2>로 구한 평균 => 4*10^1 + 8.5*10^0 = 48.5

(어메이징 수학)

---

📝 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N;
char board[5][35];
vector<vector<int> > number_shape = { {7, 5, 5, 5, 7}
                                    , {1, 1, 1, 1, 1}
                                    , {7, 1, 7, 4, 7}
                                    , {7, 1, 7, 1, 7}
                                    , {5, 5, 7, 1, 1}
                                    , {7, 4, 7, 1, 7}
                                    , {7, 4, 7, 5, 7}
                                    , {7, 1, 1, 1, 1}
                                    , {7, 5, 7, 5, 7}
                                    , {7, 5, 7, 1, 7} };

vector<vector<int> > number_change = { {0, 1, 4, 5, 7}
                                     , {1, 5, 7}
                                     , {7}
                                     , {7}
                                     , {4, 5, 7}
                                     , {5, 7}
                                     , {7}
                                     , {7} };


vector<int> line = {0, 0, 0, 0, 0};
int pos_have[9][10];
double pos_sum[9];
int pos_cnt[9];
int pos = 0;

void number_check() {
    for (int i = 0; i < 10; i++) {
        if (line == number_shape[i]) {
            if (!pos_have[pos][i]) {
                pos_have[pos][i] = 1;
                pos_sum[pos] += i;
                pos_cnt[pos]++;
            }
        }
    }
}

void number_scan(int h) {
    number_check();
    if (h > 5) {
        return ;
    }
    int line_num = line[h];
    for (int i = 0; i < number_change[line[h]].size(); i++) {
        line[h] = number_change[line[h]][i];
        number_scan(h+1);
        line[h] = line_num;
    }
}

void possible_num() {
    for (; pos < N; pos++) {
        int p = 4*pos;
        for (int h = 0; h < 5; h++) {
            int line_num = 0;
            for (int w = p; w < p+3; w++) {
                line_num *= 2;
                if (board[h][w] == '#') {
                    line_num += 1;
                }
            }
            line[h] = line_num;
        }
        number_scan(0);
    }
}

void calc() {
    double sum = 0;
    int size = 1;
    for (int i = 0; i < N; i++) {
        sum += (pos_sum[i]/pos_cnt[i])*pow(10, N-i-1);
        size *= pos_cnt[i];
    }
    cout << fixed;
    cout.precision(5);
    if (size == 0) cout << -1;
    else cout << sum;

}


int main() {
    /* INPUT */
    cin >> N;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 4*N-1; j++) {
            cin >> board[i][j];
        }
    }

    /* SOLUTION */
    possible_num();
    calc();
    return 0;
}