[백준][C++] 1089: 엘리베이터

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

 

고장났을수도 있는 엘리베이터 숫자를 보고 가능한 후보 숫자들의 평균을 구하는 문제입니다.

각 자리수마다 숫자를 판별하는건 귀찮지만 어렵지는 않습니다. 0~9까지 모양을 배열로 만들어서 하나씩 체크하면 됩니다.

고장난 부분도 고려를 해서 가능한 숫자 후보를 뽑아야 합니다. 원래 숫자에서는 불이 꺼져있는데 엘리베이터에서는 불이 켜져있는 부분이 있다면 그 숫자는 불가능합니다. 불이 고장나면 꺼지기만 하기 때문입니다.

 

그 외 고려해야 하는 사항이 몇 가지 있습니다.

 

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

1. 숫자로 만들 수 없는 경우

고장난 불이 있을 수도 있는데 고장난 불은 꺼지기만 하고 켜지지 않는게 켜지는 사항은 없습니다. 그래서 위 모양처럼 가능한 숫자가 없는 경우 -1을 출력합니다

 

9
..#...#...#...#...#...#...#...#...#
...................................
..#...#...#...#...#...#...#...#...#
...................................
..#...#...#...#...#...#...#...#...#

2. 시간초과

위 케이스의 경우 출력은 499999999.5 입니다.

각 자리수마다 0~9가 들어올 수 있고, 최대 9자리가 되니까 브루트포스로 가능한 수를 전부 만들면 시간초과가 나옵니다.

그러니 자리수마다 평균을 구하고, 그 값들을 더해 전체 수의 평균을 구해야 합니다.

예를 들어 n=2, 십의 자리수 후보가 (6, 8, 9), 일의 자리수 후보가 (0, 3, 8, 9)라고 하면 avg(6,8,9)*10 + avg(0,3,8,9) 이 값이 전체 평균이 됩니다.

 

#pragma GCC optimize ("Ofast")

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


int n;
bool on[5][35];
constexpr bool NUMBERS_SHAPE[10][5][3] = {
	{ // 0
		{1,1,1},
		{1,0,1},
		{1,0,1},
		{1,0,1},
		{1,1,1},
	},
	{ // 1
		{0,0,1},
		{0,0,1},
		{0,0,1},
		{0,0,1},
		{0,0,1},
	},
	{ // 2
		{1,1,1},
		{0,0,1},
		{1,1,1},
		{1,0,0},
		{1,1,1},
	},
	{ // 3
		{1,1,1},
		{0,0,1},
		{1,1,1},
		{0,0,1},
		{1,1,1},
	},
	{ // 4
		{1,0,1},
		{1,0,1},
		{1,1,1},
		{0,0,1},
		{0,0,1},
	},
	{ // 5
		{1,1,1},
		{1,0,0},
		{1,1,1},
		{0,0,1},
		{1,1,1},
	},
	{ // 6
		{1,1,1},
		{1,0,0},
		{1,1,1},
		{1,0,1},
		{1,1,1},
	},
	{ // 7
		{1,1,1},
		{0,0,1},
		{0,0,1},
		{0,0,1},
		{0,0,1},
	},
	{ // 8
		{1,1,1},
		{1,0,1},
		{1,1,1},
		{1,0,1},
		{1,1,1},
	},
	{ // 9
		{1,1,1},
		{1,0,1},
		{1,1,1},
		{0,0,1},
		{1,1,1},
	},
};

vector<int> candidates(int idx) {
	vector<int> ret;
	for (int i = 0; i < 10; ++i) {
		bool flag = true;

		for (int j = 0; j < 5 && flag; ++j) {
			for (int k = 0; k < 3 && flag; ++k) {
				if (on[j][k + idx] && !NUMBERS_SHAPE[i][j][k])
					flag = false;
			}
		}

		if (flag)
			ret.push_back(i);
	}
	return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;

	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 4 * n - 1; ++j) {
			char ch;
			cin >> ch;

			on[i][j] = (ch == '#');
		}
	}

	vector<vector<int>> cands;
	for (int i = 0; i < 4 * n - 1; i += 4) {
		cands.push_back(candidates(i));
	}

	for (auto& v : cands) {
		if (v.empty()) {
			cout << -1 << '\n';
			return 0;
		}
	}

	double avg = 0;
	int exp = 1;
	for (auto rit = cands.rbegin();
		rit != cands.rend();
		++rit, exp *= 10) {
		avg += (accumulate(rit->begin(), rit->end(), 0) / (double)rit->size()) * exp;
	}

	cout << fixed << setprecision(6) << avg << '\n';

	return 0;
}

저는 bool로 변환하고 이것저것 삽질을 좀 해놨는데 그냥 문자열 비교로 하는게 편합니다.

문제에 주어지는 0~9 그거 복사해서 char 2차원 배열로 만들고 그걸로 비교하세요.