백준 1089. 스타트링크 타워

https://www.acmicpc.net/problem/1089

1089번: 스타트링크 타워

 

주어지는 안내판을 각 자리수로 분리하고 모든 자리수들을 전구로 표시된 1~9 숫자와 비교해서 각 자리수 마다 가능한 숫자들을 찾으면 된다. 이때 '.'로 표시된 불이 꺼진 부분은 그냥 켜버릴수 있으므로 안내판이 '.'인 경우는 무시해도 된다.

 

그 후에는 처음에는 dfs로 모든 경우를 구해줬는데 시간초과가 났다.

생각해보니 총 9자리가 존재하고 각 자리가 1~9가 될수도 있으므로 브루트포스로 구하면 시간초과가 난다.

 

찾아보니까 모두 더하지 않고도 평균을 구하는 방법이 있었다.

자리수끼리의 평균을 구하고 해당 자리수를 곱해준 값들을 더해주면 된다.

 

예를들어 10의 자리수에서 가능한 수 : 0, 8

예를들어 1의 자리수에서 가능한 수 : 8, 9 라면 

전체 평균 = avg(0,8) * 10 + avg(8, 9) * 1 가 된다.