1089번: 엘리베이터
가능한 것은 8, 9, 88, 89
www.acmicpc.net
처음에는 상당한 구현량이 있다고 생각했으나 조금 더 고민해보니 그냥 '구현할 부분이 아주 없진 않다'정도로 수월해졌던 문제이다.
위와 같이, 숫자를 만들기 위한 전구의 위치에 번호를 매겨, 하나의 숫자를 번호 집합으로 표현할 수 있게 된다. 위의 그림은 3을 예시로 들었다. 아래는 3을 번호 집합으로 표현한 것이고, 그 아래 주황색처럼 표시가 되었다면, 그 숫자는 사실 3일 수 있다는 뜻이다.
문제에서 켜져야 하는 전구가 꺼질 수는 있지만, 꺼져야 하는 전구가 켜지진 않는다고 하였다.
이에 대해 점으로 표시된 부분을 일일이 켜보면서 숫자 대조를 해볼 수도 있겠지만, 효율적이지 않다.
대신에, 주어진 표시등을 표현하는 숫자 집합이 각 정상 숫자 집합에 포함되는지 여부만 확인하면 된다.
3의 정상적 숫자 집합은 {0,1,2,5,6,7,8,11,12,13,14}이며, {0,2,5,6,12,13,14}는 그에 포함되기에, 그림에서의 표시등은 3이었을 수도 있다는 뜻이 된다.
이렇게 하여 각 위치에 따라 가능한 숫자들을 모두 구했을 때,
문제에서 N은 최대 9이고, 각 위치에 올 수 있는 숫자는 최대 10가지이다. (0~9)
총 10의 9승의 경우의 수가 있게 되고, 이는 10억이다. 일일이 다 구해서 다 더하고 평균을 구하는 건 불가능하다. 이것이 문제에서 왜 일일이 가능한 층 수를 출력하지 않고, 평균만 구하라고 했는지에 대한 이유이다. 사실 총합이나 평균 등을 구하는 건 훨씬 빠르게 가능하기 때문이다. 사실 이걸 생각하는 게 더 어려운 부분이 아닐까 ...
아래의 예시를 보자.
위에서와 같이 각 자리에 올 수 있는 숫자들이 정해졌을 때, 총 경우의 수는 18가지가 된다. (3 곱하기 2 곱하기 3)
첫 번째 자리에 1이 오는 경우는 몇 가지가 있을까? 첫 번째 자리에 1이 왔을 때 만들 수 있는 숫자는 그림과 같이,
123, 128, 129, 133, 138, 139 총 6가지이다.
이 6이라는 숫자는 2 곱하기 3으로도 나오지만, 18 나누기 3으로도 구할 수 있다.
18 나누기 3은 총 가지수 나누기 현재 자리에 올 수 있는 숫자의 개수이다.
이렇게 하는 이유는 어떠한 자리에서 등장 횟수(이 예시에서는 6)를 구할 때, 다른 자리들에서의 모든 가지 수를 합산하는 O(n) 연산을 배제하기 위해서이다. 100은 6번이 나오니, 총합을 구하기 위해 600을 누적해준다. 이런 방식으로 총합을 구하는 것이다.
이렇게 하여 모든 숫자들마다 등장 횟수만큼 (자릿수에 따른 10의 배수처리도 필요, 백의 자리면 100, 십의 자리면 10) 합산해주고 마지막에 총 가지수로 나눠주면 평균을 구할 수 있게 된다.
즉, 위의 예시에서는
(100+400+500)*6 + (20+30)*9 + (3+8+9)*6 = 6000 + 450 + 120 = 6570이 총합이 되고,
6570 / 18 = 평균이 되고, 이것이 곧 답이 된다.
[10의 9승] 연산이 [9곱하기 10 + 9] 연산으로 크게 줄었다!
O(10^n) -> O(10n + n)
이렇게 하여 시간 내에 답을 구할 수 있다.
<주요 내용>
경우의 수, 부분 집합, 구현, 숫자 집합
<코드>
파이썬 set의 메서드인 intersection을 사용하여 부분집합인지를 판단하였다.
숫자와 숫자 간에 공백이 있음에 주의한다. (idx=4*i)를 하는 이유.
import sys
si = sys.stdin.readline
elev, possibleNums = [], []
nums = [set() for _ in range(10)]
nums[0] = {0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 14}
nums[1] = {2, 5, 8, 11, 14}
nums[2] = {0, 1, 2, 5, 6, 7, 8, 9, 12, 13, 14}
nums[3] = {0, 1, 2, 5, 6, 7, 8, 11, 12, 13, 14}
nums[4] = {0, 2, 3, 5, 6, 7, 8, 11, 14}
nums[5] = {0, 1, 2, 3, 6, 7, 8, 11, 12, 13, 14}
nums[6] = {0, 1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14}
nums[7] = {0, 1, 2, 5, 8, 11, 14}
nums[8] = {0, 1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14}
nums[9] = {0, 1, 2, 3, 5, 6, 7, 8, 11, 12, 13, 14}
def check(idx, pos):
temp = set()
for c in range(3):
for r in range(5):
if elev[r][idx+c] == '#':
temp.add(r*3+c)
for i in range(10):
if nums[i].intersection(temp) == temp:
possibleNums[pos].append(i)
def main():
global elev, possibleNums
n = int(si())
elev, possibleNums = [si()[:-1] for _ in range(5)], [[] for _ in range(n)]
for i in range(n):
idx = 4*i
check(idx, i)
total, pnlist = 1, []
for i, e in enumerate(possibleNums):
total *= len(e)
s = 0
for elem in e:
s += elem
pnlist.append([s*10**(n-i-1), len(e)])
if not total:
print(-1)
return
s = 0
for e in pnlist:
s += e[0]*total//e[1]
print(s/total)
if __name__ == '__main__':
main()
