[백준 1089] 스타트링크 타워 (Python)

문제 :

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

1089번: 스타트링크 타워

 

Step 1. 문제 이해하기

• 자릿수가 9자리가 나올 수 있고 한 자릿수마다 0 ~ 9의 숫자가 올 수 있음.
• 나올 수 있는 모든 숫자 조합의 합을 구하고 평균을 구해야 하는 문제.
• 9자리를 브루트 포스로 모든 경우의 수를 구하면 시간 초과가 발생할 수 있음.

 

Step 2. 문제 풀이 생각하기

1. 자릿수마다 나올 수 있는 숫자를 판별해야겠다고 생각했고, 9자리의 조합할 수 있는 모든 숫자를 알지 않아도 평균을 구할 수 있는 방법이 뭐가 있을까 생각했습니다.
2. 평균을 구할 때 (자릿수에 나올 수 있는 수의 합) * (10 ** (해당 자릿수의 0의 개수)) 을 자릿수마다 구하고 다 더한 다음, 모든 경우의 수로 나누면 더 빠르게 구할 수 있다고 생각했습니다.
3. 먼저 해시 테이블 형태로 숫자마다 '.'인 좌표를 넣습니다. -> '#'보다 '.'으로 비교하는 것이 더 빠르다고 판단했습니다.
4. 전체 그래프의 (3*5)씩 잘라서 자릿수마다 숫자의 '.'의 위치에 좌표와 일치하는 개수를 카운트합니다.
5. 카운트가 일치하면 자릿수마다의 개수를 담는 리스트과 자릿수마다의 합을 저장한 리스트 각각을 갱신합니다.
6. 그래프를 (0, 0)에서 4씩 오른쪽으로 옮기면서 4~5를 반복합니다.
7. ans에 (해당 자릿수 총합) * (해당 자릿수가 나오는 개수)를 모든 자릿수에 대해서 총합을 구하고 모든 경우의 수로 나눈 값을 저장합니다.

 

Step 3. 차근차근 구현하기

import sys
input = sys.stdin.readline
n = int(input())
g = [list(map(str, list(input().strip()))) for _ in range(5)]
numOfNum = [0 for _ in range(n)] # 해당 자릿수에 나올 수 있는 숫자 개수
sumOfNum = [0 for _ in range(n)] # 해당 자릿수에 나올 수 있는 숫자들의 합
totalNum = 1 # 나올 수 있는 경우의 수
ans = 0 # 정답

# 숫자 별 '.'이 들어가 있는 좌표를 해시에 저장
numHt = { 0 : [[1, 1], [2, 1], [3, 1]],
          1 : [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1], [3, 0], [3, 1], [4, 0], [4, 1]],
          2 : [[1, 0], [1, 1], [3, 1], [3, 2]],
          3 : [[1, 0], [1, 1], [3, 0], [3, 1]],
          4 : [[0, 1], [1, 1], [3, 0], [3, 1], [4, 0], [4, 1]],
          5 : [[1, 1], [1, 2], [3, 0], [3, 1]],
          6 : [[1, 1], [1, 2], [3, 1]],
          7 : [[1, 0], [1, 1], [2, 0], [2, 1], [3, 0], [3, 1], [4, 0], [4, 1]],
          8 : [[1, 1], [3, 1]],
          9 : [[1, 1], [3, 1], [3, 0]]
}

nj = 0 # 맵을 오른쪽으로 4씩 옮기기 위한 새로운 j값
for idx in range(n):
    for num in range(10):
        numValueArr = numHt[num] # 숫자별 모든 '.'의 좌표
        cnt = 0 
        for i, j in numValueArr:
            j = nj + j
            # 그래프상의 '.' 좌표와 한 숫자마다의 '.' 좌표가 일치하면 cnt를 1증가
            if g[i][j] == '.':
                cnt += 1
            # 그 개수가 숫자의 개수와 일치할 때
            if cnt == len(numValueArr):
                sumOfNum[idx] += num * (10 ** (n - idx - 1)) # num(0 ~ 9 중 하나) * (해당 자릿수가 가지는 0의 개수) 를 해당 자릿수 번째에 넣기
                numOfNum[idx] += 1 # 해당 자릿수의 개수를 1증가
    nj = nj + 4

for i in range(n):
    numSum = 1
    for j in range(n):
        if i != j:
            numSum *= numOfNum[j] # 해당 자릿수가 나오는 개수
        if i == 0:
            totalNum *= numOfNum[j] # 나올 수 있는 총 숫자 개수
    ans += sumOfNum[i] * numSum # 해당 자릿수 총합 * 해당 자릿수가 나오는 개수

# 아무 경우도 나올 수 없는 예외 처리
if totalNum == 0:
    print(-1)
    exit(0)
print(ans / totalNum)

 

Step 4. 피드백

• 평균을 구할 때 어떤 식으로 빨리 구할 수 있는지 배웠고, 구현 문제는 하드코딩을 해야 하는 상황도 있으므로 문제를 빠르게 파악하고 풀이를 진행하는 것이 중요하다는 것을 배웠습니다.