백준 33870 빗질의 중요성 / python

문제 : 33870

풀이 point

상태를 지정한다. 엉키지 않음, 엉킴, 엉키었으나 한번 풀음

2가지 방법이 있다.

1. 하루하루마다 강아지를 보면서 상태들을 갱신해나간다.
2. 강아지마다 빗질한 날짜를 얻은 후, 강아지마다 상태들을 갱신한다.

나는 첫번째 방법으로는 잘 되지 않아 두번째 방법으로 진행하였다.

다 하고 보니 첫번째 방법 때 빗질을 하지 않는 강아지들을 갱신하지 않아서 제대로 되지 않았던거였다. 아쉽다.

풀이 방법

강아지마다 빗질한 날짜를 얻은 후, 강아지마다 상태들을 갱신해나간다.
지정해놓은 상태를 통해 엉키지 않음, 엉킴, 엉키었으나 한번 풀음 상태로 바꾸어 나간다.
이때 엉키었으나 한번 풀고, 그 다음 완전히 엉킴이 풀릴려면 이틀 연속으로 빗질을 해주어야한다.(1, 2 연속으로 해주어야함 - 날짜가 띄워져있으면 안됨)

강아지를 빗질한 마지막 날을 갱신해나가면서 상태를 보면 된다.

코드

#백준 33807, 빗질의 중요성

N, M = map(int, input().split())

dogs = list(map(int, input().split()))

days = list(map(int, input().split()))

combs = [[] for _ in range(N)]
for d, dog in enumerate(days, start=1):
    combs[dog-1].append(d)

status = [0] * N   #0 풀림, 1 엉킴

ans = 0

for i in range(N):
    k = dogs[i] #강아지 엉킴 일수
    last = 0 #마지막 날
    con = 0 #엉킴 풀기 확인
    state = 0

    for d in combs[i]:
        if state == 0 and d - last - 1 >= k:
            state = 1
            con = 0

        if state == 1 and con == 1 and d == last + 1: #엉킴 연속 빗질 풀기
            state = 0

        con = 1 if state == 1 else 0

        last = d #마지막 일수 업뎃

    if state == 0 and (M - last) >= k : state = 1 #M+1 계산

    if state == 1: ans += 1

print(ans)