백준 16567 바이너리 왕국 파이썬 반례 O

 

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

16567번: 바이너리 왕국

flip 횟수를 0이 나올때마다 구하면 시간초과가 나올 수 밖에 없는 문제이다.

0 > 1 로 바꿔줄때 flip 횟수를 구해야 시간초과를 피할 수 있다! 

밑에는 반례입니다. 코드 설명은 아래에 하겠습니다.

입력
5 9
0 1 0 0 0
0
1 1
0
1 3
0
1 5
0
1 2
0

답
1
1
1
2
2

오답
0
0
0
1
1

핵심 포인트 정리입니다.

1.  양 옆이 1인 경우 1 0 1 -> 1 1 1 flip해줘야하는 경우가 1번 감소해count-=1

2.  양 옆이 0인 경우 0 0 0 -> 0 1 0 flip해줘야하는 경우가 1번 증가해 count+=1

3.  한 쪽만 1인 경우 0 0 1 -> 0 1 1 flip해줘야하는 경우가 변경 X

4.  양 끝부분은 한 부분만 비교해야 해서 if 문으로 따로 예외처리를 해줌. 

정답코드입니다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
s = list(map(int,input().split()))
count = 0
e = 0

for i in range(n): #초기 count를 구해주는 동작 안해주면 0만 가득한 리스트를 제외하고는 틀림. ex반례
    if s[i] == 0:
        e = 0
    elif s[i] == 1:
        if e ==0:
            count+=1
            e = 1
            
for i in range(m):
    a = list(map(int,input().split()))
    if a[0] == 1 and s[a[1]-1] == 0:
        a[1]-=1
        if a[1] == 0:
            if s[1] ==0:
                count+=1
                s[a[1]] = 1
                
        elif a[1] == n-1:
            if s[n-2] ==0:
                count+=1
                s[a[1]] = 1
        else:
            if (s[a[1]-1] == 1 and s[a[1]+1] == 1): #1번
                count-=1
                s[a[1]] = 1
                    
            elif (s[a[1]-1] == 0 and s[a[1]+1] == 0): #2번
                s[a[1]] = 1
                count+=1
            else: #3번
                s[a[1]]=1
    
    elif a[0]==0:
        print(count)