[BOJ] 20055 컨베이어 벨트 위의 로봇

n, k = list(map(int,input().split()))
conveyer = list(map(int,input().split()))
robot = [0]*n
robot_cnt = 1
step = 0
while conveyer.count(0) < k:
    last_number = conveyer.pop()
    conveyer.insert(0,last_number)
    last_robot = robot.pop()
    robot.insert(0,0)
    robot[n-1] = 0
    que = []
    for i in range(n):
        if robot[i] > 0:
            que.append([robot[i],i])
    que.sort()
    while que:
        robot_ind, ind = que.pop(0)
        if ind + 1 == n-1:
            if conveyer[n-1] != 0:
                robot[ind+1] = 0
                robot[ind] = 0
                conveyer[n-1] -= 1
            else:
                robot[ind] = robot_ind 
        else:
            if conveyer[ind+1] != 0 and robot[ind+1]==0:
                robot[ind+1] = robot_ind
                robot[ind] = 0
                conveyer[ind+1] -= 1
            else:
                robot[ind] = robot_ind
    if robot[0] == 0 and conveyer[0]:
        robot[0] = robot_cnt
        robot_cnt += 1
        conveyer[0] -= 1
    step += 1
print(step)

 

첫 풀이는 문제에서 robot에는 로봇의 최초진입시기를 저장해주고, conveyer에는 컨베이어의 내구도를 적어주는 것이다.

먼저 컨베이어 벨트가 움직이고 n-1 위치에 도착시 로봇이 바로 내려가는 것만 주의해주면 어렵지 않은 문제였다. 하지만 시간이 오래걸리는 문제가 있으므로, 밑의 방식으로 개선했다.

 

 

 

from collections import deque

n, k = map(int, input().split())
arr = list(map(int, input().split()))
ls = [['X'] for _ in range(2*n)]
for i in range(2*n):
    ls[i].append(arr[i])
belt = deque(ls)

lift_idx = 0
drop_idx = n-1
cnt = 0 
result = 0
while True:
    #내구도가 0인게 k개 이상인지 카운트해서 while문 탈출조건을 세워준다.
    if cnt >= k:
        break
    # 벨트 돌아가기
    tmp = belt.pop()
    belt.appendleft(tmp)
    # 내릴 수 있으면 내린다.
    if belt[drop_idx][0] == 'O':
        belt[drop_idx][0] = 'X'
    #이동이 가능하면 이동한다.
    for i in range(n-2,-1,-1):
        if belt[i][0] == 'O':
            if belt[i+1][0] == 'X' and belt[i+1][1] != 0:
                belt[i][0] = 'X'
                belt[i+1][0] = 'O'
                belt[i+1][1] -= 1
                if i+1 == drop_idx:
                   belt[i+1][0] = 'X'
    #로봇을 올린다.
    if belt[lift_idx][1] != 0 and belt[lift_idx][0] == 'X':
        belt[lift_idx][0] = 'O'
        belt[lift_idx][1] -= 1
    cnt = 0
    for i in range(len(belt)):
        if belt[i][1] == 0: 
            cnt += 1
    result += 1
                
print(result)

belt의 i번째는 해당 index에 로봇이 있는지 유무와 belt의 내구도를 저장해준다.

그리고 어차피 n-1에서 모든 로봇은 내려가므로, n-2 부터 0까지 반복문을 돌려주면 차례대로 이동하는 것이 된다.

이 부분만 바뀌고 나머지는 동일하다.