[Python] 31064: Cowntact Tracing 2

31064: Cowntact Tracing 2

풀이

1. 최대 일수

먼저 현재 주어진 상태가 최대 며칠째의 상태일 수 있는지를 구해야 한다.

연속된 1 덩어리들의 크기를 별도의 배열에 저장한다. 최대 일수를 구할 때, 왼쪽이나 오른쪽 끝에 붙어있는 덩어리는 다른 덩어리들과 동일하게 처리하여야 편하다. 양쪽 끝에 붙어있지 않다고 가정하기 위해 * 2 - 1을 해준다.

가장 작은 덩어리가 최대 일수의 기준이 되므로, 가장 작은 덩어리를 기준으로 최대 일수를 구하는 식을 찾아보면

1. 만약 5칸짜리 덩어리가 있다면, 그 덩어리는 최대 2일째에 가능한 크기이다.
   00100
01110
11111

2. 만약 6칸짜리 덩어리가 있다면, 그 덩어리는 최대 2일째에 가능한 크기이다.
   001100
011110
111111

3. 만약 7칸짜리 덩어리가 있다면, 그 덩어리는 최대 3일째에 가능한 크기이다.
   0001000
0011100
0111110
1111111

위 예시들을 통해서, (가장 작은 덩어리의 크기 - 1) // 2가 가능한 최대의 일수라는 것을 알 수 있다.

2. 시작 시점에서 1의 최소 개수

최대 일수를 구했으므로, 이제 시작 시점에서 1의 최소 개수를 구해야 한다.

일수가 2일이라고 가정하면, 하나의 1로는 2일 후에 5칸을 채울 수 있다.
00100
01110
11111

즉 하나의 1로는 day * 2 + 1칸을 1로 만들 수 있으므로, 덩어리 / (day * 2 + 1)를 올림한 값이 각 덩어리가 필요로 하는 최소 1의 개수이다. sum하여 답을 구한다.

코드

from math import ceil
import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
bits = list(map(int, input()))

mass = []
i = 0
while i < n:
    if bits[i] == 1:
        count = 0
        while i < n and bits[i] == 1:
            count += 1
            i += 1
        mass.append(count)
    else:
        i += 1

if sum(mass) == 0:
    print(0)
    exit(0)

temp = mass[:]
if bits[0] == 1:
    temp[0] = temp[0] * 2 - 1
if bits[-1] == 1:
    temp[-1] = temp[-1] * 2 - 1
day = ((min(temp) - 1) // 2)

for i in range(len(mass)):
    mass[i] = ceil(mass[i] / (day * 2 + 1))

print(sum(mass))