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

Thumbnail: Photo by charlesdeluvio (Unsplash)

애완견의 빗질은 항상 잊지 말고 해줍시다~

풀이

​구현

별다른 어려움 없이, 문제 조건을 그대로 구현하면 되는 문제였습니다. 다만, 답을 맞히기까지 여러 차례 시행착오를 겪었습니다..

털 상태 관리

1일차부터 \(M\)일차 까지 강아지 1마리씩 골라 빗고, 만약 이전에 빗은 날로부터 일정 주기가 지나면 강아지의 털이 엉키며, 털이 엉킨 강아지는 2일 연속으로 빗어야 빗어집니다.

먼저, 털을 빗은 날을 저장하는 길이 \(N\)의 int형 배열 combed를 만들고, 0으로 초기화합니다. 털이 엉켰는지 상태를 저장하는 길이 \(N\)의 bool형 배열 tangled를 만듭니다.

다음으로, 1일차부터 \(M\)일차까지 for문으로 반복하며, 다음을 반복합니다:

• \(N\)마리의 강아지의 오늘의 털 상태를 계산합니다.
  • 이때 엉킴 처리도 같이 진행합니다.
• 이후, 오늘 빗은 강아지(dog)에 대해 다음을 진행합니다:
  • 만약 dog의 털이 엉킨 상태이고, 어제 빗은 강아지도 dog라면 털의 엉킨 상태를 해제한다.
• combed[dog]을 오늘 날짜로 갱신합니다.

전체 코드

input = open(0).readline
N, M = map(int, input().split())
DURATION = tuple(map(int, input().split()))
# 배열 인덱스에 맞게 1 줄인다.
PLAN = tuple(map(lambda x: int(x) - 1, input().split()))

# 털이 엉켰는지 여부 저장
tangled = [False for _ in range(N)]
# 마지막으로 빗질한 날짜 저장
combed = [0 for _ in range(N)] 

# 1일차부터 M일차까지 순회하면서...
for day in range(1, M + 1):
    for i in range(N):
        if not tangled[i] and day -  combed[i] > DURATION[i]:
            tangled[i] = True
    
    dog = PLAN[day - 1]
    # 엉킨 상태이며 2일 연속으로 빗질했다면
    if tangled[dog] and combed[dog] == day - 1:
        tangled[dog] = False
    combed[dog] = day

# 결과 출력 (M+1일차에 엉키는 경우를 처리해준다.
cnt = 0
for i in range(N):
    if not tangled[i] and M + 1 -  combed[i] > DURATION[i]:
        tangled[i] = True
    if tangled[i]:
        cnt += 1
print(cnt)

시행착오

첫 구현은, 단일 배열에 각 강아지의 털이 엉키기까지 남은 일수를, 엉켰다면 며칠 더 빗어야 하는지를 기록했습니다. 그러나 57% 부근에서 틀렸습니다를 받고 말았습니다...

아마 엉킨 당일에 빗질하는 경우의 처리가 문제였던 것으로 보입니다. 더불어, 모든 배열을 매 반복마다 수정하는건 그리 좋은 방법도 아닌 것 같아서, 코드를 변경했습니다.

from functools import reduce
input = open(0).readline
N, M = map(int, input().split())
DURATION = tuple(map(int, input().split()))
PLAN = tuple(map(lambda x: int(x) - 1, input().split()))    # 배열 인덱스에 맞게 1 줄인다.

status = [DURATION[i] for i in range(N)]  # 양의 정수: 빗질하고 아직 여유가 있음. / 0: 기한 안에 빗질을 안한 상태. 이 상태에서 빗질을 해도 엉킴. / 음의 정수: 엉켜있음. 2일 연속 빗질 시 DURATION[i]로 초기화.
for i in PLAN:
    if status[i] == -2: # 엉켜있는 상태에서 처음 빗질한 경우.
        status[i] = -1
    elif status[0] == 0:
        status[i] = -2
    else: # 2일 연속 빗질한 경우 / 아직 엉키기 전인 경우
        status[i] = DURATION[i]
    
    for j in range(N):
        if i == j:
            continue
        if status[j] > 0:
            status[j] -= 1
        elif status[j] == 0:
            status[j] = -2
        elif status[j] == -1:   # 엉킨 상태에서는 연속으로 빗질하지 않으면 엉킨다.
            status[j] = -2

print(reduce(lambda acc, s: acc + (1 if s <= 0 else 0), status, 0))  # 엉킨 상태가 아닌 경우의 수를 세어 출력한다.