1. 문제
-
1~3 과정 중 n번 칸 위치에 사람이 위치하면 즉시 하차
-
각 칸의 안정성은 시간이 지남에 따라 다시 상승하지 않음
-
ex) 각 칸의 안정성 = 2, 0인 칸이 1 이상일 때 실험 종료
-
위 과정이 1번의 실험
⇒ 과정이 종료될 때 몇 번째 실험을 하고 있었는지?
-
2. 풀이
-
시뮬레이션 : 조건문과 엣지 케이스를 고려하자
- 무빙워크의 각 위치별 안정도를 담은 배열 `stability` - `stability[0]` : 0번째 위치의 안정도 - 실험에 참여한 사람에 대한 정보를 담은 배열 `people` - `people[0]` : 0번째 위치에 사람이 있으면 1, 없으면 0 - zeros 변수로 안정도가 0인 위치의 개수를 추적하여 simulate가 끝난 후 zeros가 k이상이 되면 실험 종료 (while 반복문 탈출)
- simulate 함수 1회 = 실험 1회
- 무빙워크를 이동시킨 후, (stability배열,people배열 모두 회전)
- n번칸에 사람이 있으면 (people[n-1] == 1) 하차시키기- 사람 이동 시키기 - 현재 index 전에 사람이 있고, 현재 위치에 사람이 없고, 안정도가 0보다 클 경우 이동 - 이동 : - `stability[index] -=1` - `people[index] = 1` - `people[index-1] = 0` - `stability[index] == 0`이면 `zeros+1` - 이동 후에도 n번칸에 사람이 있으면 내리기 - 0번째 칸에 (사람은 이동해서 비어있을 것이므로) 안정도가 0보다 크면 사람 새롭게 올리기 - 이 행위로 0번째 칸의 안정도가 0이 되면 `zeros + 1`
3. 코드
from collections import deque
n, k = map(int, input().split())
stability = deque(list(map(int, input().split())))
people = deque([0 for i in range(n)])
zeros = 0
def simulate():
global zeros
# 무빙워크 이동
stability.appendleft(stability.pop())
people.appendleft(people.pop())
# n번칸 사람 내리기
if people[n - 1]:
people[n - 1] = 0
# 사람 이동
for i in range(n - 1, 0, -1):
# 현재 위치에 사람이 없고 내구도는 남아 있으면서 이전 위치에 사람이 있는 경우
if people[i] == 0 and people[i - 1] and stability[i]:
people[i] = 1
people[i - 1] = 0
stability[i] -= 1
if stability[i] == 0:
zeros += 1
# n번칸 사람 내리기
if people[n - 1]:
people[n - 1] = 0
# 사람 올리기
if stability[0]:
stability[0] -= 1
people[0] = 1
if stability[0] == 0:
zeros += 1
answer = 0
while True:
simulate()
answer += 1
if zeros >= k:
break
print(answer)+α
- 1차 시도 : 실패 - 시간 초과, 문제 해석 오류
- people이라는 빈 list에 사람을 append하는 방식, people[0]은 1번째 사람의 위치
n, k = map(int, input().split()) stability = list(map(int, input().split())) zeros = stability.count(0) people = [] # people[0] = location on moving walk of 1st person exp = 0 stop = False while True: exp += 1 #rotate stability = [stability[-1]] + stability[1:2*n-1] #move people on moving walk for idx, p in enumerate(people): if p == n-1: people.pop(i) elif p + 1 in people or stability[p+1] == 0: continue else: people[idx] += 1 stability[p+1] -= 1 if stability[p+1] == 0: zeros +=1 if zeros >= k: stop = True break if not stop and 0 not in people: people.append(0) stability[0] -= 1 if stability[0] == 0: zeros += 1 if zeros >= k: stop = True if stop: break print(exp)
- people이라는 빈 list에 사람을 append하는 방식, people[0]은 1번째 사람의 위치
참고
