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

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

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

 

간단한 시뮬레이션 문제이다.

나는 생각을 어렵게 해서 쌩 배열로 구현해서 그런지 구현이 빡셌지만.. 난이도 매기는 사람들 의견보니 구현은 쉬운편이라고..

그냥 덱 자료구조로 하면 더 쉽게 할 수 있을 것 같다.

 

Python 리스트 (배열) 사용 풀이

배열과 리스트는 다르지만 사실상 리스트를 배열처럼 활용하여 풀었다.

 

나는 2N 개의 배열을 미리 잡아두고 '올리는 위치(put_pos)' 가 벨트의 몇 번 인덱스인지를 저장하는 식으로 회전을 구현하였다.

 

그리고 특정 인덱스에서 다음 인덱스를 계산하는 함수를 작성했다.

이 함수가 필요한 이유는 뒤에 나온다..

 

 

이제 반복문을 돌면서 문제에 나온 스텝을 따라간다.

첫번째로 회전은 put_pos 를 한칸 뒤로 미는 것으로 구현하였다.

컨베이어 벨트의 '윗' 부분은 put_pos 부터 N 개의 칸을 세면 된다.

 

문제에서 로봇이 '내리는 위치' 에 도착하는 즉시 로봇이 내린다고 하였으므로, 내리는 위치의 벨트를 비워준다.

로봇이 있든 없든 그냥 False 로 처리하면 되므로, 조건문은 필요하지 않다.

 

 

다음으로 로봇이 벨트 위에서 이동하는 부분을 구현해보자.

이 부분 구현이 이 문제에서 제일 어려운 구현이다.

 

먼저 put_pos 올리는 위치를 기준으로 '내리는 위치'의 벨트 인덱스를 미리 계산해둔다.

먼저 올라간 로봇부터 이동해야 하므로, 벨트의 뒷쪽부터 앞으로 오면서 순회해야 한다.

이때 실제 인덱스를 사용하면 1 0 n-1, n-2, ... 이런 순으로 경계를 넘는 부분을 순회하기가 복잡하다.

그래서 put_pos 를 그냥 N 더한 다음, 그 값을 감소시키되, 그 값으로부터 실제 인덱스를 계산해 로봇 위치를 특정하였다.

이때 실제 인덱스를 계산하는 함수가 위에서 작성한 get_next_pos 함수이다.

 

벨트 위를 순회하면서 로봇이 있을 때, 이동을 시킬 수 있으면 이동을 시키고 내구도를 감소시킨다.

 

=> 순회하는 시점에 로봇이 내리는 위치에 있었다면 이동을 시켜도 안되고, 내구도도 감소시키면 안되지 않나요?

이를 위해서 1번 단계에서 미리 벨트를 회전하며 로봇을 내려두었다.

따라서 순회하는 시점에는 '내리는 위치' 에는 반드시 로봇이 비어있다.

(사실 그래서 애초에 순회할 때 put_pos 를 N-1 만큼만 더하고 돌아도 된다.)

 

내구도가 감소할 때마다 해당 칸의 내구도가 0인지 확인해서 zero_count도 세준다.

zero_count 가 K 이상이면 즉시 루프를 벗어난다.

(사실 이 반복문 내의 모든 '스텝' 이 하나의 단계 내부이고, 문제에서는 마지막 '단계' 를 출력하면 되기 때문에 zero_count 는 반복문 맨 마지막에 한번만 체크해줘도 된다.)

 

 

다음 단계로는 새로운 로봇을 '올리는 위치' 에 올려주고 단계 카운트를 세주면 끝이다.

 

아래는 전체 코드이다.

N, K = map(int, input().split())
durabilities = list(map(int, input().split()))
zero_count = durabilities.count(0)

is_robot = [False] * (2*N)
put_pos = 0 # 로봇이 올라가는 벨트 위치
level = 1

DEBUG = False

def print_belt(l):
    pos = put_pos
    for _ in range(N):
        print(l[pos], end=' ')
        pos += 1
        pos %= (2*N)
    print()
    _l = []
    for _ in range(N):
        _l.append(l[pos])
        pos += 1
        pos %= (2*N)
    print(*reversed(_l))


def debug_print(step):
    if not DEBUG:
        return
    print(level, step)
    print(put_pos)
    print_belt(is_robot)
    print_belt(durabilities)
    print(f"zero count: {zero_count}")
    print()


def get_next_pos(now_pos):
    while now_pos >= 2*N:
        now_pos %= (2*N)
    next_pos = now_pos + 1
    next_pos %= (2*N)
    return next_pos


while zero_count < K:
    # 1. rotate
    put_pos -= 1
    put_pos += (2*N)
    put_pos %= (2*N)

    is_robot[(put_pos + N - 1) % (2 * N)] = False  # 내리는 위치는 일단 무조건 내리고 봄.

    debug_print(1)

    # 2. move robots
    down_pos = (put_pos+N-1)%(2*N)
    for i in range(put_pos+N-1, put_pos-1, -1):
        next_pos = get_next_pos(i)
        if not is_robot[i%(2*N)]:
            continue
        #print(i, next_pos)

        if not is_robot[next_pos] and durabilities[next_pos]:
            is_robot[i % (2 * N)] = False
            if next_pos != down_pos:
                is_robot[next_pos] = True

            durabilities[next_pos] -= 1
            if durabilities[next_pos] == 0:
                zero_count += 1

    debug_print(2)
    if zero_count >= K:
        break

    # 3. put new robots
    if durabilities[put_pos]:
        is_robot[put_pos] = True
        durabilities[put_pos] -= 1
        if durabilities[put_pos] == 0:
            zero_count += 1
            if zero_count >= K:
                debug_print(3)
                break

    debug_print(3)

    level += 1

if DEBUG:
    print("answer")
print(level)

 

덱 사용 풀이

덱을 사용하면 풀이가 아주 간단해진다.

귀찮은 인덱스 관리할 필요 없이 is_robot, durability 모두 그냥 rotate 시켜주면 된다.

인덱스 대신 rotate 를 사용한 것을 제외하면 로직이 위와 동일하므로 코드 첨부로 간단히 정리한다.

 

from collections import deque

N, K = map(int, input().split())
durabilities = deque(list(map(int, input().split())))
zero_count = durabilities.count(0)

is_robot = deque([False] * (2*N))
level = 1

DEBUG = False


def print_belt(l):
    pos = 0
    for _ in range(N):
        print(l[pos], end=' ')
        pos += 1
        pos %= (2*N)
    print()
    _l = []
    for _ in range(N):
        _l.append(l[pos])
        pos += 1
        pos %= (2*N)
    print(*reversed(_l))


def debug_print(step):
    if not DEBUG:
        return
    print(level, step)
    print_belt(is_robot)
    print_belt(durabilities)
    print(f"zero count: {zero_count}")
    print()


while zero_count < K:
    # 1. rotate
    is_robot.rotate(1)
    durabilities.rotate(1)

    is_robot[N-1] = False

    debug_print(1)

    # 2. move robots
    for i in range(N-2, -1, -1):
        if not is_robot[i]:
            continue

        if not is_robot[i+1] and durabilities[i+1]:
            is_robot[i] = False
            if i+1 != N-1:
                is_robot[i+1] = True

            durabilities[i+1] -= 1
            if durabilities[i+1] == 0:
                zero_count += 1

    debug_print(2)
    if zero_count >= K:
        break

    # 3. put new robots
    if durabilities[0]:
        is_robot[0] = True
        durabilities[0] -= 1
        if durabilities[0] == 0:
            zero_count += 1
            if zero_count >= K:
                debug_print(3)
                break

    debug_print(3)

    level += 1

if DEBUG:
    print("answer")
print(level)