[Python] 백준, 20055 (구현)

https://www.acmicpc.net/problem/20055

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

 

개요

• 문제를 이해하는 게 가장 어려웠던 문항
• 정말 "구현" 문제인게 원하는 대로 따라가다보면 정답에 도달하는 구성
  • 해야할 것만 차근차근 해나가는 느낌
  • 조건 놓치지 않는 꼼꼼함이 이런 류의 문제에 가장 필요하지 않나

 

해결 방법

1. 문제에는 2차원 배열로 표시되어 있지만 1차원 배열로도 충분히 구현 가능
   • weight : 내구도 배열
   • robots : 로봇 위치 배열 ~ 존재하면 1, 아니면 0 
     • 한 칸에 두 개 이상의 로봇이 존재해도 되는지에 대한 조건이 주어지지 않아 일단 고려하지는 않았는데 정답이 나오기는 함
2. weight, robots 배열 회전
   • 많은 방법이 있겠지만, pop()의 시간 복잡도를 믿고 저렇게 작성하긴 함
   • 정답 후에 생각해보니 올리는 위치와 내리는 위치 인덱스를 -1 칸씩 갱신해주는 방법도 있음
     • 이렇게 하는게 가장 깔끔하고 효율적일 것 같음
3. 로봇의 역순으로 for 문 순회
   • 로봇 위치 기준, i + 1 칸의 로봇이 존재하지 않고, 내구도가 0 보다 크면 한칸 이동
   • 이 때 내리는 위치인지에 따라 조건 잘 나눠야 함
4. 내구도 배열의 첫 칸이 0보다 크다면 로봇 올려줌

 

Python Code

import sys

n, k = map(int, sys.stdin.readline().split())
weight = list(map(int, sys.stdin.readline().split()))
robots = [0] * (2 * n)

result = 0

while True:
    # 1단계
    # 2차원 배열로 진행하면 복잡해질 것 같아 그냥 1차원 배열로 정의
    # 시간 복잡도는 어떻게 될지 모르겠으나 deque 사용은 싫어서 임의로 회전 (맨 앞에 요소 추가) 정의
    weight = [weight.pop(), *weight]
    robots = [robots.pop(), *robots]
    # 언제든 로봇이 내리는 위치에 도착하면 즉시 내림
    robots[n - 1] = 0

    # robots 배열에 들어있는 로봇의 위치 역순으로 확인 (먼저 들어간 로봇부터)
    for i in range(n - 1, -1, -1):
        if robots[i] == 1:      # 로봇이 존재할 경우
            if (weight[i + 1] > 0) and (robots[i + 1] == 0):
                weight[i + 1] -= 1
                robots[i] = 0
                # 언제든 로봇이 내리는 위치에 도착하면 즉시 내림
                if (i + 1) == n - 1:
                    robots[i + 1] = 0
                else:
                    robots[i + 1] = 1

    if weight[0] > 0:
        robots[0] = 1
        weight[0] -= 1

    # 과정 테스트
    # print(weight)
    # print(robots)
    # print('\n')

    result += 1

    if weight.count(0) >= k:
        break


print(result)