백준 1089. 스타트링크 타워

tose33 2022. 9. 9. 13:33

1089번: 스타트링크 타워

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

www.acmicpc.net

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

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

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

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

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

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

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

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