문제 링크: https://www.acmicpc.net/problem/16567

Thumbnail: Photo by Gonzalo Facello (Unsplash)

생각 외의 부분에서 실수했던 문제였습니다 :P

풀이

알고리즘 구상

단순히 1 i꼴의 명령을 받으면 배열의 그 원소만 1로 바꾸고, 출력할 때 마다 배열을 순회하게 되면 \(O(NM)\) 꼴이 되며, 시간 초과가 발생합니다.

따라서, 1 i의 명령을 받을 때 미리 결과를 계산해 두고, 0에서는 그냥 미리 계산한 값을 출력해주기만 하는 방식으로 접근해야 합니다.

• 초기 입력
  • 도로의 상태를 탐색해, 몇 번의 flip이 필요한지 미리 계산해둡니다.
• 쿼리 수행
  • 1 i의 명령을 받을 시, 필요한 flip의 횟수를 다시 계산합니다.
  • 0의 명령을 받을 시, 미리 계산해 둔 flip의 횟수를 출력합니다.

초기 상태 탐색

도로의 각 칸을 순회하며, '연속된 1' 이 몇 번 등장하는지 판단합니다.

이때, 다음 원소와 비교하기 위해 \(0 ~ N-1\)만큼 반복하므로 마지막 칸에 대한 처리가 부족합니다. 따라서, for문 이후에 마지막 칸에서도 1이 연속되었는지를 확인해 개수에 포함시켜줍니다.

input = open(0).readline
N, M = map(int, input().split())
road = list(map(int, input().split()))
cnt = 0

# 최초 도로의 상태 확인
checking = False
for i in range(N - 1):
    if not checking and road[i] == 1:
        checking = True
    if checking:
        if road[i + 1] == 0:
            cnt += 1
            checking = False
if checking:
    cnt += 1  # 마지막 그룹이 끝나지 않은 경우

쿼리 수행

1) 도로 더럽히기

도로를 더럽힐 때, 이로 인해 발생할 수 있는 변화는 다음과 같습니다.

• flip이 1회 더 필요해진다
• flip의 횟수에 변화가 없다 (기존 1에 연속해서 붙음)
• flip의 횟수가 1 줄어든다 (기존 2개의 연속된 1을 이어줌)

value = int(query[2:]) - 1
if road[value] == 1:  # 이미 더럽혀진 칸이라면 아무런 작업도 수행하지 않는다. 
    continue

if value > 1 and road[value - 1] == 1:  # 왼쪽이 더러운 경우
    if value < N - 1 and road[value + 1] == 1:
        cnt -= 1    # 오른쪽도 더러운 경우, 두 그룹이 하나로 합쳐지므로 개수 감소.
    # 왼쪽만 더럽고 오른쪽은 깨끗한 경우는 기존 그룹에 붙는 것이므로 개수 변화 없음.

elif value < N - 1 and road[value + 1] == 1:  # 오른쪽이 더러운 경우
    if value > 0 and road[value - 1] == 1: 
        cnt -= 1    # 왼쪽도 더러운 경우, 두 그룹이 하나로 합쳐지므로 개수 감소.
    # 왼쪽만 더럽고 오른쪽은 깨끗한 경우는 기존 그룹에 붙는 것이므로 개수 변화 없음.

else:  # 양쪽 모두 깨끗한 경우, 새로운 그룹이 생김.
    cnt += 1

road[value] = 1

0) 횟수 출력하기

미리 계산해둔 flip의 횟수(cnt) 를 출력해주면 된다.

if query[0] == "0":
    print(cnt)

전체 코드

input = open(0).readline
N, M = map(int, input().split())
road = list(map(int, input().split()))
cnt = 0

checking = False
for i in range(N - 1):
    if not checking and road[i] == 1:
        checking = True
    if checking:
        if road[i + 1] == 0:
            cnt += 1
            checking = False
if checking:
    cnt += 1

for _ in range(M):
    query = input().strip()
    if query[0] == "0":
        print(cnt)
    else:
        value = int(query[2:]) - 1
        if road[value] == 1:
            continue

        if value > 1 and road[value - 1] == 1:
            if value < N - 1 and road[value + 1] == 1:
                cnt -= 1 
        elif value < N - 1 and road[value + 1] == 1:
            if value > 0 and road[value - 1] == 1:
                cnt -= 1
        else:
            cnt += 1
        road[value] = 1