[백준]1089 엘리베이터 #7segment #digit

1.풀이

합이나 평균을 구할때 수학적 사고를 하자!

​

(1) i번째 숫자가 (0~9중)될 수 있는 모든 수를 찾는다.

ex) digitLSize=[[1],[0,8],[8,9]] => 100의자리에 1이 올 수 있고, 10의자리는 0,8이 올 수 있고, 1의자리는 8,9가 올 수 있다.

​

(2) 될 수 있는 모든 경우의 수를 찾는다.

* dfs로 완전탐색하려 했지만 메모리 초과가 났다(소스코드1)

* 각자리에 올 수 있는 숫자를 나올수 있는 횟수만큼 더하면 총 합을 구할 수 있다. (소스코드2)

위의 예시에서 100의 자리 1은 총 2*2번나오므로 100*1*4,

10의자리 0은 총 1*2번나으모르 10*0*2...

​

2. 소스코드

(1) 소스코드1 (메모리초과)

import sys
sys.setrecursionlimit(10**8)

N=int(input())
board=[]
for i in range(5):
    board.append(input())

sample=["###...#.###.###.#.#.###.###.###.###.###",
        "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
        "#.#...#.###.###.###.###.###...#.###.###",
        "#.#...#.#.....#...#...#.#.#...#.#.#...#",
        "###...#.###.###...#.###.###...#.###.###"]

# r,c로 시작하는 숫자를 0~9까지 비교한다.
def compare(num):
    c=num*4
    numL=[]
    for sampleNum in range(10):
        sampleC=sampleNum*4
        isPossible=True
        for i in range(5):
            for j in range(3):
                if board[i][c+j]=="#" and sample[i][sampleC+j]==".":
                    isPossible=False
                    break
            if not isPossible:
                break
        if isPossible:
            numL.append(sampleNum)
    return numL

def dfs(digit,nowNum):
    if digit==N:
        intNowNum=int(nowNum)
        if visited[intNowNum]==0:
            ansL.append(intNowNum)
            visited[intNowNum]=1
        return
    for num in digitL[digit]:
        dfs(digit+1,nowNum+str(num))

digitL=[]
for j in range(N):
    if board[1][j*4+1]=="#" or board[3][j*4+1]=="#":
        print(-1)
        sys.exit()
    digitL.append(compare(j))

ansL=[]
visited=[0 for i in range(int("9"*N)+1)]
dfs(0,"")
print(sum(ansL)/len(ansL))

 

(2) 소스코드2 (통과)

import sys
sys.setrecursionlimit(10**8)

N=int(input())
board=[]
for i in range(5):
    board.append(input())

sample=["###...#.###.###.#.#.###.###.###.###.###",
        "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
        "#.#...#.###.###.###.###.###...#.###.###",
        "#.#...#.#.....#...#...#.#.#...#.#.#...#",
        "###...#.###.###...#.###.###...#.###.###"]

# r,c로 시작하는 숫자를 0~9까지 비교한다.
def compare(num):
    c=num*4
    numL=[]
    for sampleNum in range(10):
        sampleC=sampleNum*4
        isPossible=True
        for i in range(5):
            for j in range(3):
                if board[i][c+j]=="#" and sample[i][sampleC+j]==".":
                    isPossible=False
                    break
            if not isPossible:
                break
        if isPossible:
            numL.append(sampleNum)
    return numL

digitL=[]
for j in range(N):
    if board[1][j*4+1]=="#" or board[3][j*4+1]=="#":
        print(-1)
        sys.exit()
    digitL.append(compare(j))

digitLSize=[len(digitL[i]) for i in range(N)]
totalCase=1
for i in digitLSize:
    totalCase*=i

total=0
for i in range(N):
    tenFold = 10 ** (N - i - 1)
    cnt=totalCase//digitLSize[i]
    for t in digitL[i]:
        total+=t*tenFold*cnt
print(total/totalCase)