[백준 BOJ / Python] 1089번 스타트링크 타워

문제

5*3 개의 전구를 통해 0~9까지의 숫자를 표현할 수 있을 때,

전구가 망가졌을 수도 있음을 가정하고, 켜진 전구들을 살펴보아 만들 수 있는 숫자들의 평균을 구하는 문제이다.

층 안내판의 크기는 5*3 판을 여러 개 이어 붙인 형태이며 판 사이의 꺼진 전구가 존재한다.

풀이

• 먼저 문제에서 주어진 0~9까지의 표현을 가지고 5*3 판 위의 어떤 전구가 켜졌을 때 어떤 숫자를 만들 수 있는지 판별해야 한다.
  • 예를 들어 5*3 판을 기준으로 (0,0) 위치의 전구가 켜지면 만들 수 있는 숫자들(0,2,3,4,5,6,7,8,9)을 저장한다.
  • 같은 간격으로 숫자가 있기에 (i, j+k*4)를 통해 동일한 위치의 전구들을 확인할 수 있다.
• 각각의 판이 만들 수 있는 숫자들을 추출한다.
  • 만약 (3,0) 위치의 전구가 켜져 있다면 {0, 2, 6, 8} 숫자들을 만들 수 있으며,
  • 그리고 (3,2) 위치의 전구가 켜져 있다면 {0, 1, 3, 4, 5, 6, 7, 8, 9} 숫자들을 만들 수 있다.
  • (3,0)과 (3,2) 전구가 동시에 켜져 있다면 두 집합의 교집합인 {0, 6, 8} 숫자들을 만들 수 있다.
• 앞에서부터 숫자들의 평균을 더해주면 전체 평균을 구할 수 있다.
  • n = 2 일 때, 앞의 숫자 후보들은 {0, 6, 8}이고, 뒤의 숫자 후보들은 {0, 2, 8}이라면,
  • 평균은 (0+6+8)/4 * 10 + (0+2+8)/3 = 38.33333이다.
  • 앞의 숫자 후보들의 평균에 계속해서 10을 곱해줌으로써 자릿수를 부여할 수 있다.

Python 코드

import sys
input = sys.stdin.readline
n = int(input())

# 문제에서 주어진 숫자 표현
numbs = """###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###""".split()

# 전구의 위치에 따라 만들 수 있는 숫자 후보
can_make = dict()

def make_candidates():
    for i in range(5):
        for j in range(3):
            can_make[(i,j)] = set()
            # 만들 수 있는 숫자라면 추가
            for k in range(10):
                if numbs[i][j+k*4] == "#":
                    can_make[(i,j)].add(k)

def sol():
    numb = [input() for _ in range(5)]
    res = 0.0
    for s in range(n): # 앞에서부터 5*3 판을 훑음
        can_ = set(range(10)) # 초기에는 모든 숫자를 만들 수 있다 가정
        for i in range(5):
            for j in range(s*4,s*4+3):
                if numb[i][j] == "#":
                    can_ &= can_make[(i,j%4)] # 해당 전구가 켜졌을 때 만들 수 있는 숫자와 교집합을 구함
        
        # 해당 5*3 판에서 만들 수 있는 숫자들의 평균을 구하여 더해준다.
        # 앞의 수부터 더했기 때문에 *10을 통해 자릿수를 맞춘다.
        if can_:
            res *= 10
            res += sum(can_)/len(can_)
        else:
            res = -1
            break # 한 개라도 후보자가 없다면 망가진 안내판이다.

    print(res)
    
make_candidates()
sol()

 

문제출처

1089번: 스타트링크 타워