b_컨테이너벨트_20055

문제

• 1에서올릴수있음
• 로봇을 올리거나 칸 이동시 해당칸 내구도 -1
• 다른칸으로 이동하려면 로봇이 없으면서 내구도가 1이상
• 0인 칸의 개수가 k이상일시 종료
• N에서 내림 ,내릴 수 있을 시 즉시내림
  순서

1. 벨트자체가이동(칸자체가이동)
2. 로봇이 한칸식이동
3. 올리는곳(1)에내구도1이상이면올림
4. 내구도 0 인거개수새서 k개이상이면 다시 1

종료시 몇번을 돌았나 ( 순서를 한번으로 치는듯)

답 (시간초과 ver)

import sys
from collections import deque

pointer = False # false면앞에서읽기 true면뒤에서 읽기

N,K = map(int,sys.stdin.readline().strip().split())
belt = deque(map(int,sys.stdin.readline().strip().split()))
robot  = deque([0] * N * 2)
result = 1

while True :
    # 회전
    belt.rotate(1)
    robot.rotate(1)

    # 로봇이동
    i = N*2 - 1
    while i >= 0: 
        if i >= N-1:
            robot[i] = 0
        elif robot[i] != 0:
            nexti = (i + 1) % (N*2)
            if robot[nexti] == 0 and belt[nexti] > 0:
                robot[i] = 0
                robot[nexti] = 1
                belt[nexti] -= 1
        i -= 1

    # 올리기
    if robot[0] == 0 and belt[0] > 0:
        robot[0] = 1
        belt[0] -= 1
    
    healt_cnt = 0

    for i in range(N*2):
        if i >= N-1:
            robot[i] = 0
        if belt[i] < 1:
            healt_cnt += 1
        if healt_cnt >= K:
            break
    if healt_cnt >= K:
        break
    result += 1
    
print(result)

정답

주요 요점은 재귀를 쓰지말고 while을 써서 재귀깊이를 초과하지 않으며,
내구도 체크를 이동시에만 체크하는 식으로 진행을 하여 시간복잡도를 줄이고 0~N-1까지만 반복문을 돈다

import sys
from collections import deque

pointer = False # false면앞에서읽기 true면뒤에서 읽기

N,K = map(int,sys.stdin.readline().strip().split())
tmp = sys.stdin.readline().strip().split()
healt_cnt = 0
belt = deque([])
for t in tmp:
    nt = int(t)
    belt.append(nt)
    if nt < 1:
        healt_cnt += 1


robot  = deque([0] * N * 2)
result = 1

while True :
    # 회전
    belt.rotate(1)
    robot.rotate(1)
    robot[N-1] = 0

    # 로봇이동
    i = N - 2
    while i >= 0: 
        if robot[i] != 0:
            nexti = (i + 1) % (N*2)
            if robot[nexti] == 0 and belt[nexti] > 0:
                robot[i] = 0
                robot[nexti] = 1
                belt[nexti] -= 1
                
                robot[N-1] = 0
                if belt[nexti] < 1:
                    healt_cnt += 1
        i -= 1

    # 올리기
    if robot[0] == 0 and belt[0] > 0:
        robot[0] = 1
        belt[0] -= 1
        if belt[0] < 1:
            healt_cnt += 1
    
    if healt_cnt >= K:
        break
    result += 1
    
print(result)