[백준] (33517) 징검다리 게임 [Python]

문제 링크

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

문제

상혁이는 징검다리 게임을 하고 있다. 이 게임에는 N개의 칸으로 구성된 징검다리가 있으며, 플레이어는 첫 번째 칸에서 출발하여 마지막 칸에 도달하면 게임에서 승리한다.

징검다리의 각 칸은 비어 있거나 곰 또는 지뢰 중 하나가 존재하며, 모든 곰의 체력은 1 이상의 정수이다. 또한 첫 번째 칸과 마지막 칸은 비어 있다. 징검다리 게임의 명령어는 아래와 같다.

• 점프 (J): 다음 칸으로 이동한다. 이동한 칸에 곰이나 지뢰가 있다면 플레이어는 패배한다.
• 공격 (A): 다음 칸에 있는 곰의 체력을 1 깎는다. 곰의 체력이 0이 되면 다음 칸의 곰은 사라진다. 다음 칸이 빈칸이라면 아무 일도 일어나지 않으며, 다음 칸에 지뢰가 있다면 지뢰가 폭발하여 플레이어는 패배한다.
• 지뢰 제거 (D): 다음 칸에 있는 지뢰를 제거한다. 다음 칸에 지뢰가 없다면 아무 일도 일어나지 않는다.

상혁이는 징검다리 게임에서 승리하기 위해 키 매크로를 개발했다. 키 매크로는 점프(J), 공격(A), 지뢰 제거(D)로 구성된 길이 K의 문자열을 입력받으면 문자열의 첫 번째 명령어부터 차례대로 실행한다. 마지막 명령어를 수행한 이후에는 첫 번째 명령어부터 다시 실행한다. 명령어를 10¹⁰⁰회 실행했을 때 마지막 칸에 도달하지 못했다면 플레이어는 패배하며, 키 매크로는 실행 중 게임에서 승리하거나 패배할 경우 즉시 종료된다.

징검다리의 상태와 상혁이가 입력한 문자열이 주어졌을 때, 상혁이가 마지막 칸에 도달하여 게임에서 승리할 수 있다면 YES, 승리할 수 없다면 NO를 출력하시오.

---

오답 코드

from sys import stdin
input = stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
K = input().strip()
alive = True
pos = 0
limit = 10 ** 100
afk = 0

for i in range(limit):
    cmd = K[i % M]
    if pos+1 >= N-1:
        if cmd == 'J':
            break
        else:
            continue
    if cmd == 'J':
        if A[pos+1] != 0:
            alive = False
            break
        else:
            pos += 1
            afk = 0
    elif cmd == 'A':
        if A[pos+1] > 0:
            A[pos+1] -= 1
        elif A[pos+1] == -1:
            alive = False
            break
        afk += 1
    else:
        if A[pos+1] == -1:
            A[pos+1] = 0
        afk += 1
    if afk == M:
        alive = False
        break

print("YES" if alive else "NO")

• 결과: 시간 초과 (TLE)
• 이유: K의 길이(M)가 최대 1,000,000이고 징검다리(N)가 500,000개이므로, 매번 명령어를 한 글자씩 확인하는 O(N × 필요한 명령어 수) 방식은 1초 안에 해결할 수 없다.
• 해결 방법: 일일이 명령어를 수행하는 것 대신 인덱스 점핑을 통해 다음에 어떤 인덱스의 징검다리 돌에 이동하게 되는지를 계산하면서 계산 횟수를 줄였다.
  1. 전처리: 명령어 문자열 K에서 J, A, D가 등장하는 위치(인덱스)를 각각 리스트에 저장한다.
  2. 위치 계산: 현재 매크로의 실행 위치가 pos일 때, n번째 뒤에 나오는 특정 명령어('A' 등)의 절대 위치를 계산하는 함수를 정의한다.
  3. 생존 판정:
     • 곰(체력 H): H번의 'A'가 필요하다. H번째 'A'가 나오는 위치를 찾는다. 그 전에 'J'가 나온다면 패배한다.
     • 지뢰: 1번의 'D'가 필요하다. 첫 번째 'D'가 나오는 위치를 찾는다. 그 전에 'J'나 'A'가 나온다면 패배한다.
     • 빈칸: 장애물을 처리한 후(또는 원래 빈칸이면), 다음 'J'를 찾아 이동한다.

정답 코드

from bisect import bisect_left
from sys import stdin
input = stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
K = input().strip()
alive = True
pos = 0

if 'J' not in K:
    print("NO")
    exit()

JAD = {'J': [], 'A': [], 'D': []}
for i in range(M):
    JAD[K[i]].append(i)

has_bear = False
for i in range(N):
    if A[i] > 0:
        has_bear = True
        break
if has_bear and not JAD['A']:
    print("NO")
    exit()

has_mine = False
for i in range(N):
    if A[i] == -1:
        has_mine = True
        break
if has_mine and not JAD['D']:
    print("NO")
    exit()

def find_target(char, cur, cnt):
    jad = JAD[char]
    L = len(jad)
    if L == 0:
        return float('inf')

    start_pos = bisect_left(jad, cur % M)
    rem = L - start_pos
    if cnt <= rem:
        return (cur // M) * M + jad[start_pos + cnt - 1]
    else:
        nxt_rem = cnt - rem
        nxt_start = ((cur // M) + 1) * M
        return nxt_start + ((nxt_rem - 1) // L) * M + jad[(nxt_rem - 1) % L]

for i in range(N-1):
    if A[i+1] == -1:
        d_pos = find_target('D', pos, 1)
        j_pos = find_target('J', pos, 1)
        a_pos = find_target('A', pos, 1)
        if j_pos < d_pos or a_pos < d_pos:
            alive = False
            break
        pos = d_pos + 1
    elif A[i+1] > 0:
        kill_pos = find_target('A', pos, A[i+1])
        j_pos = find_target('J', pos, 1)
        if j_pos < kill_pos:
            alive = False
            break
        pos = kill_pos + 1
    j_pos = find_target('J', pos, 1)
    pos = j_pos + 1

print("대상혁" if pos > 10**100 else ("YES" if alive else "NO"))

 

이분 탐색 메서드 bisect_left의 동작 방식은 아래와 같다.

• 해당 값이 리스트에 있을 때: 해당 인덱스를 반환
• 해당 값이 리스트에 없을 때: 리스트 오름차순에 들어갈 인덱스를 반환

from bisect import bisect_left

arr = [1, 3, 5, 7, 9]
print(bisect_left(arr, 5)) # 2
print(bisect_left(arr, 2)) # 1