[백준/파이썬] 20055번 컨베이어 벨트 위의 로봇

문제 주소: https://www.acmicpc.net/problem/20055

20055번: 컨베이어 벨트 위의 로봇

문제 해석

문제

문제 풀이

문제 설명에 애매한 부분이 존재해서 좀 애먹었다.

 

먼저 컨테이너 벨트는 위 아래로 존재한다.

시계 방향으로 회전하며, N의 위치에 도달하면 N+1로 2N의 위치에 도달하면 1의 위치로 시계 방향으로 회전한다.

-> 이 부분을 보자마자 deque를 떠올려 구현했다.

 

1번 칸은 "올리는 위치" 이며, N번 칸은 "내리는 위치" 이다.

내리는 위치에 도달한 로봇은 즉시, 내리게 된다.

a) 이러한 조건 때문에 로봇의 이동 범위는 1 ~ N칸 이다.

 

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.

-> 이 경우 큐의 가장 우측 값을 좌측에 넣어주면 O(1)의 시간으로 모든 값을 회전시킬 수 있다.

2. 가장 먼저 벨트에 올라간 로봇부터, 시계 방향으로 이동할 수 있다면 한 칸 이동한다.

-> a)의 조건에 따라 가장 먼저 벨트에 올라간 로봇은 N 위치에 존재한다. 따라서 N~1 방향으로 체크하며 로봇을 이동시켜 준다.

 

문제 코드

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
temp = list(map(int, input().split()))
belt = deque(temp)
robots = deque([0] * (n * 2))
TAKE, OUT = 0, n - 1

def out_robot():
    robots[OUT] = 0

def location():
    belt.appendleft(belt.pop())
    robots.appendleft(robots.pop())
    out_robot()

def robot_move():
    for i in range(OUT - 1, -1, -1):
        cur = i
        next = i + 1
        if robots[cur] == 1:
            if belt[next] > 0 and robots[next] == 0:
                belt[next] -= 1
                robots[next], robots[cur] = 1, 0
    out_robot()

def robot_take():
    if robots[TAKE] == 0 and belt[TAKE] > 0:
        belt[TAKE] -= 1
        robots[TAKE] = 1

def check_zero():
    count = 0
    for i in range(n * 2):
        if belt[i] == 0:
            count += 1
    if count >= k:
        return False
    else:
        return True

answer = 1
while 1:
    location()
    robot_move()
    robot_take()

    if check_zero():
        answer += 1
    else:
        break
print(answer)

제출 결과

입력 부분을 잘 구현하자.
트리의 지름을 구하는 문제는 잊을만 하면 풀게 되는 것 같다..