[python] 백준 20055 - 컨베이어 벨트 위의 로봇

출처 : 백준, https://www.acmicpc.net/problem/20055

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

 

 

먼저, 생각해야 할 부분

 

1. 문제를 잘 이해하자.

 

문제가 너무 이상하지만 차근차근 읽어보면 해석이 된다.

문제에서 말하는 단계란 무엇일까?

# 단계의 정의 -> 1~4까지가 1단계
        # 1. 벨트를 움직인다. -> 로봇 내림
        # 2. 로봇을 움직인다. -> 내구도 하락 및 로봇 내림
        # 3. 로봇 올림
        # 4. 내구도 k개인지 조사

 

이것이 문제에서 말하는 하나의 단계이다.

즉, 이 과정을 몇 번 반복했는지 계산하는 문제이다.

 

2. 강한 어조가 나오면 기억하자.

 

아무 생각 없이 풀다가 실수한 부분인데 문제에서 강조하는 부분이 하나 있다.

'언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.'

이렇게 강조하는 부분이 나오면, 예외처리를 해줘야할지도 모른다는 것을 기억하자.

---

 

풀이

 

def solution(n, k, endurance):
    step = 0
    robot_location = [0] * (2 * n)
    OFF_LOCATION = n - 1
    ON_LOCATION = 0

    while k > 0:
        # 단계 시작
        step += 1

        # 벨트 이동
        last_element = endurance.pop()
        endurance.insert(0, last_element)

        last_robot = robot_location.pop()
        robot_location.insert(0, last_robot)

        # 내리는 위치 검사
        if robot_location[OFF_LOCATION]:
            robot_location[OFF_LOCATION] = 0

        # 로봇 이동
        for i in range(OFF_LOCATION - 1, -1, -1):
            #벨트 위 영역에 대해서 로봇이 있는 곳에서 로봇이 이동 가능하다면
            if robot_location[i] and not robot_location[i + 1] and endurance[i + 1] > 0:
                # 로봇 이동
                robot_location[i] = 0
                robot_location[i + 1] = 1
                endurance[i + 1] -= 1

                # 이동한 타일의 내구도가 0이면 k 감소
                if endurance[i + 1] == 0:
                    k -= 1

        # 내리는 위치 검사
        if robot_location[OFF_LOCATION]:
            robot_location[OFF_LOCATION] = 0

        # 시작 위치에 로봇을 올릴 수 있다면,
        if not robot_location[ON_LOCATION] and endurance[ON_LOCATION] > 0:
            robot_location[ON_LOCATION] = 1
            endurance[ON_LOCATION] -= 1

            # 로봇을 올린 타일의 내구도 검사
            if endurance[ON_LOCATION] == 0:
                k -= 1

    return step

n, k = map(int, input().split())
endurance = list(map(int, input().split()))

print(solution(n, k, endurance))

 

---

시간복잡도와 제한 시간

원래 시간복잡도를 적는 공간인데, 제한 시간 충족 여부를 적어보고 싶어서 바꿨다.

사실 잘 모르는데 어떻게 계산하는걸까 고민하면서 적어보는거라 틀릴 수도 있다.

 

while문으로 감싸는데 최대 내구도 * 최대 밸트 타일 개수만큼 while문이 회전할 것이다.

따라서 최악의 경우는 n이 100이고, 이에 따라 k는 200이 된다.

또, 취대 타일의 내구도가 1000이므로, while문의 시간 복잡도는 1000 * k = 1000 * 2 * n이라 O(n)일 것이다.

 

while문 내부의 알고리즘은

 

1. 밸트 회전 : O(n)

2. for문 : O(n)

 

이 있으므로, O(n)이다.

 

따라서, O(n) * O(n)으로 O(n^2)이라 추측해볼 수 있다.

 

그렇다면 위 알고리즘이 제한 시간인 1초 안에 돌 수 있을까?

Python은 1초에 2천만번의 계산을 할 수 있다고 한다.

이에 따라 Python에서의 제한시간과 N의 크기를 매칭해봤을 때, 1초라면

 

O(N)	10,000,000
O(NogN)	100,000
O(N^2)	2,000
O(N^3)	500

출처 : 이것은 취업을 위한 코딩테스트다

정도로 규정하고 있다.

이 경우 n은 최대 100이므로 1초 안에 풀 수 있는 문제가 될 것이다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들

 

Reference