[백준-파이썬] 14465: 소가 길을 건너간 이유 5

소가 길을 건너간 이유 5

후기 🤗

이 문제를 풀면서 슬라이딩 윈도우, 스위핑!! 이라는 것을 처음 들어봤다. 그래서 기억할 겸 간단하게라도 후기와 코드를 올린다.
전에 귀여운 라이언 문제를 풀 때도 투 포인터로 풀었었는데, 슬라이딩 윈도우랑 투 포인터랑 비슷한 느낌이다.

스위핑은 특정한 자료구조로 푸는 것은 아니고, 한번만 쭉 스캔해서 해결하는 기법이라고 한다.
투 포인터는 1차원 배열에서 두 개의 포인터(보통 시작점, 끝점인 것 같다)를 이용해서 문제를 푸는 것이다.
슬라이딩 윈도우는 투 포인터와 비슷한데, 항상 시작점과 끝점 사이 간격이 똑같은 경우라고 한다.

라이님의 블로그 글을 보니까 이해가 잘되었다!

코드 👨‍💻

n, k, b = map(int,input().split())
min_fix = float('inf')

road = [True]*(n+1)

for _ in range(b):
    road[int(input())] = False
#print(road)

s = 1
e = 1 # 이걸 0으로 해야 맞을 것 같은데,, 1로 해야 맞고 0으로 하면 틀린다..?!!
fix = 0

# 일단 1~k 사이에 고장난 신호등을 수리하는 경우(그러면 k개니까..)
while e < k:
    e += 1
    if road[e] == False:
        fix += 1

while e < n: 
    min_fix = min(min_fix, fix)
    e += 1 # 다음부터는 s, e를 하나씩 이동해가면서
    s += 1
    if road[e] == False: # 다음 것이 고장난 신호등이면 fix 더하고
        fix += 1
    if road[s] == False: # 전에 것이 고장난 신호등이면 fix 빼고
        fix -= 1

print(min_fix)

모르는 것 🤔

e = 1 # 이걸 0으로 해야 맞을 것 같은데,, 1로 해야 맞고 0으로 하면 틀린다..?!!
이 부분은 잘 모르겠는데, 생각을 더 해보려고 한다.