[파이썬] 백준 20055 : 컨베이어 벨트 위의 로봇 (골드5)

[파이썬] 백준 20055 : 컨베이어 벨트 위의 로봇 (골드5)

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

---

문제

---

풀이

0. 방향성 생각

• 선형 구조의 시작점에서 push와 비슷한 연산이 이루어진다.
• 시간 단축을 위해서 list 대신 deque 사용
• 컨베이어 벨트 정보와 로봇 정보 따로 deque를 정의한다.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,k = map(int,input().split())
conveyor = list(map(int,input().split()))
robot = [False]*2*n

q_cv = deque(conveyor)
q_rb = deque(robot)

• 입력정보

2. rotate 함수 정의

def rotate():
    q_cv.appendleft(q_cv.pop())
    q_rb.appendleft(False)
    if q_rb[n-1]: 
        q_rb[n-1] = False
    q_rb.pop()

• 컨베이어 내구도 정보는 계속 순환한다.
• 로봇 정보는 일단 로봇을 올리기 전이니 False를 삽입한다.
• 또 이동한 로봇이 끝칸에 도달하면 False로 바꿔준다.

3. move_robot 함수 정의

 

def move_robot():
    
    global broken
    
    for i in range(n-2,-1,-1):
        if q_rb[i] and not q_rb[i+1] and q_cv[i+1]: 
            q_rb[i] = False
            q_rb[i+1] = True 
            q_cv[i+1] -= 1 

            if not q_cv[i+1]: broken += 1

• 모든 로봇이 동시에 움직이게 구현할 수 없으니, 맨 뒤에 로봇부터 순차적으로 이동시킨다.
• 현재 탐색위치에 로봇이 있고, 다음칸에 로봇이 없고 내구도가 유효하면 연산을 처리해준다.
• 로봇 이동시 컨베이어 내구도가 감소했으면 내구도가 0이 되는지 확인한다.

4. push_robot 함수 정의

def push_robot():
    
    global broken
    
    if q_cv[0]: 
        q_cv[0] -= 1
        q_rb[0] = True

        if not q_cv[0]: broken += 1

• 처음 위치 내구도가 있으면 내구도 1 감소시키면서 로봇 올리기.
• 로봇 올렸으면 내구도가 0이 되는지 체크

5. 출력

answer = 0
while True:

    rotate()
    move_robot()
    push_robot()
    answer += 1

    if broken >= k:
        print(answer)
        break

• 순차적으로 실행시키면서 broken이 처음으로 k 이상이 될 때 출력 후 탈출한다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,k = map(int,input().split())
conveyor = list(map(int,input().split()))
robot = [False]*2*n

q_cv = deque(conveyor)
q_rb = deque(robot)

broken = 0

def rotate():
    q_cv.appendleft(q_cv.pop())
    q_rb.appendleft(False)
    if q_rb[n-1]: 
        q_rb[n-1] = False
    q_rb.pop()

def move_robot():
    
    global broken
    
    for i in range(n-2,-1,-1):
        if q_rb[i] and not q_rb[i+1] and q_cv[i+1]: 
            q_rb[i] = False
            q_rb[i+1] = True 
            q_cv[i+1] -= 1 

            if not q_cv[i+1]: broken += 1

def push_robot():
    
    global broken
    
    if q_cv[0]: 
        q_cv[0] -= 1
        q_rb[0] = True

        if not q_cv[0]: broken += 1

answer = 0
while True:

    rotate()
    move_robot()
    push_robot()
    answer += 1

    if broken >= k:
        print(answer)
        break

 

코멘트

발문이 쓰레기같다.

1. 초기에 로봇을 안올리고 회전.

2. 로봇을 올린다.

3. 로봇을 이동시킨다.

초기 조건을 조금 자세하게 써줘야할듯

 

+ q_rb에 pop연산을 까먹고 안했는데 (정답에 문제는 없음) 연산을 추가해도 동작시간이 감소한다.

덱 길이가 계속 늘어나면 pop으로 지워주는게 효율이 더 올라갈듯