[백준][문자열]Startlink Tower

문제

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

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

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

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

입력

첫째 줄에 N이 주어진다. N은 9보다 작거나 같은 자연수이다. 둘째 줄부터 다섯 개의 줄에는 엘리베이터 층 번호 안내판의 상태가 주어진다. 각 문자열의 길이는 4N-1이다.

출력

첫째 줄에 층 번호 안내판이 나타내고 있다고 가정할 수 있는 모든 층 번호의 평균을 출력한다. 만약, 가능한 층 번호가 없는 경우 -1을 출력한다.

정답과의 절대/상대 오차는 10-5까지 허용한다.

예제 입력 1

1
###
#.#
###
#.#
###

예제 출력 1

8.0

8만 가능하다.

예제 입력 2

2
###.###
#.#.#.#
#.#.###
#.#...#
###.###

예제 출력 2

48.5

모든 꺼있는 전구가 고장나지 않았다고 하면 "09"를 나타내고 있는 것이다. 일부가 고장났다고 가정하면 '0'과 '9'는 모두 '8'을 나타낼 수 있다.

따라서, 가능한 층 번호는 "08", "09", "88", "89"를 표현할 수 있다. 따라서, 평균은 (8+9+88+89)/4 = 48.5이다.

예제 입력 3

2
.......
.......
.......
.......
.......

예제 출력 3

49.5

0부터 99까지 모든 층을 표현할 수 있다.

예제 입력 4

1
...
.#.
...
...
...

예제 출력 4

-1

원리

이 문제의 풀이법은 꽤 간단하다.

1. 3 X 5 크기의 문자열에서 각 문자 별로 #일때 불가능한 숫자 목록을 만든다.
2. 각 자릿수 별로 가능한 숫자 목록을 0~9로 초기화한다.
3. 입력 받은 문자열들을 분석하여 각 자릿수 별로 가능한 숫자들의 목록을 갱신한다.
   • 각 자릿수에 해당하는 문자들을 순회하면서 어떤 자리가 #이면 가능한 숫자 목록에서 그 자리가 #일 경우 불가능한 숫자 목록을 빼준다.
4. 모든 자릿수 별 가능한 숫자들의 목록을 조합해 모든 가능한 숫자들의 평균을 구한다.

시행착오

딱히 없었다.

풀이

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <list>
using namespace std;

int main() {
	int N;
	double answer = 0;
	cin >> N;
	int strlen = N * 4 - 1;
	vector<string> strings(5);
	vector<int> impossibles[5][3] //해당 자리가 #일 경우 불가능한 숫자들 목록
	{ 
		{ {1},           {1,4},   {10} },
		{ {1,2,3,7},     {-1},    {5,6} },
		{ {1,7},         {0,1,7}, {10} },
		{ {1,3,4,5,7,9}, {-1},    {2} },
		{ {1,4,7},       {1,4,7}, {10} }
	};
	vector<set<int>> possibles(N, set<int>{0,1,2,3,4,5,6,7,8,9});//각 자릿수 별 가능한 숫자 목록
	for (int i = 0; i < 5; ++i)
	{
		string s;
		cin >> s;
		strings[i] = s;
	}
	long long count = static_cast<long long>(pow(10,N));
	for (size_t i = 0; i < strlen; i+=3) // i는 i/4 번째 글자
	{
		int n = i / 4;
		if (strings[n+1][1]=='#' || strings[n+1][3] == '#') {
			cout << -1;
			return 0;
		}
		//bool ok = false;
		for (size_t j = i; j < i+3; j++) // j는 열
		{
			for (size_t k = 0; k < 5; k++) // k는 행
			{
				int row = k;
				int col = j % 4;
				if (strings[k][j] == '#') {
					for (auto q = impossibles[row][col].begin(); q != impossibles[row][col].end(); q++)
					{
						set<int>::iterator it = possibles[i / 4].find(*q);
						if (it != possibles[i / 4].end())
						{
							possibles[i / 4].erase(it);
							count--;
						}
					}
				}
			}
		}
		i++;
	}
	long long sum = 0;
	long long tmpsum = 0;
	list<int> numbers;
	for (int j = 0 ; j < N; j++)// 각 자릿수 순회 N-j번쨰 자리
	{

		for (auto sit = possibles[j].begin(); sit != possibles[j].end() ; ++sit) //각 자리수에 가능한 수 순회
		{
			sum += (*sit) * (count / (possibles[j].size()));
		}
	}
	answer = sum / static_cast<double>(count);
	cout << answer;
	cin >> N;
}